Riceova věta, triviálnost a vstupně-výstupní vlastnost

Riceova věta ukazuje nerozhodnutelnost celé třídy problémů, její znění je následující "Každá netriviální vstupně/výstupní vlastnost programů je algoritmicky nerozhodnutelná".
Program je v tomto případě tabulka (nekonečná) s dvěma sloupci: v prvním sloupci jsou všechny přípustné vstupy programu a v druhém sloupci je ke každému vstupu uveden buď příslušný výstup nebo nedefinovanost v případě, že výpočet pro vstup neexistuje.

Vstupně-výstupnost

Vlastnost X je vstupně/výstupní právě tehdy, když každé dva programy se stejnou I/O tabulkou (programem) buď oba vlastnost X mají nebo ji oba nemají. Tabulku si představme pro každý Turingův stroj s dvěma sloupci: v prvním sloupci jsou všechny přípustné vstupy programu a v druhém sloupci je ke každému vstupu uveden výstup.

Triviálnost

Každá vlastnost X rozdělí množinu všech Turingových strojů na dvě disjunktní podmnožiny: jedna je množina strojů, které vlastnost X mají, a druhá je množina strojů, které vlastnost X nemají. Z toho lze určit, že:
Vlastnost X je triviální, když je jedna ze dvou zmíněných množin prázdná, tedy buď ji mají všechny stroje mají nebo ji nemá ani jeden. Vlastnost X je netriviální, jestliže ji alespoň jeden stroj má a alespoň jeden stroj nemá. 

Rozhodnutelnost

Každá netriviální vstupně/výstupní vlastnost programů je nerozhodnutelná. Neboli je-li X netriviální vstupně/výstupní vlastností Turingových strojů, pak je příslušný problém nerozhodnutelný podle Riceovy věty. Pozor, negací nezjistíme rozhodnutelnost!

Schéma

Pouze kombinace odpovědí z tabulky dávají smysl:

Vlastnost	1	2	3
Je I/O?	A	A	N
Je triviální?	A	N	N
Je nerozhodnutelná?	N	A	N

Jak na příklady

Pro každé posouzení vlastností se ptám otázkami:

1. Poznám tuto vlastnost ze vstupně-výstupní tabulky? Pokud ano, tak je vstupně-výstupní.
2. Existuje program, který tuto vlastnost má a současně jiný program, který ji nemá? Pak není triviální.
3. Je vlastnost vstupně-výstupní a současně není triviální? Pak je nerozhodnutelná.

Konkrétní příklady jsou ve skriptech Teoretické informatiky na straně 223.