Riceho věta říká, že když zvolíme jakoukoli netriviální vlastnost, pak je nerozhodnutelné, zda jazyk akceptovaný nějakým Turingovým strojem tuto vlastnost má nebo ne. Poměrně snadno lze pomocí redukce tuto nerozhodnutelnost rozšířit i na jiné aspekty chování Turingových strojů, například zda mohou dojít do určitých konfigurací, vydat na výstup určité hodnoty a podobně. Vzpomeňme, že podle Turingovy-Churchovy teze se dá každý počítač s libovolným programem simulovat Turingovým strojem. Pak z Riceho věty vyplývá, že všechny netriviální aspekty chování počítačů a počítačových programů jsou nerozhodnutelné. To má dalekosáhlé důsledky pro ladění a testování software.
Vyčíslitelnost a složitost výpočtů
Riceho věta
Shrnutí kapitoly
Studijní materiál
Skripta P. Sosík, Teorie vyčíslitelnosti, kapitola 3.4.
Příklady a problémy
- Dokažte pomocí Riceho věty, že pro daný stroj M je nerozhodnutelné, zda L(M) =
∅ . (Ekvivalentní tvrzení: neexistuje testovací algoritmus, který by zjistil, zda testovaný program pro všechny vstupy odpoví „NE.") - Důsledkem Riceho věty například je, že pro mikroprocesorem řízenou pračku je nerozhodnutelné, zda při nastavení programu na jemné prádlo (vstup) nebude dvě hodiny jenom ždímat (výstup). Zdůvodněte nerozhodnutelnost tohoto tvrzení pomocí redukce, inspirujte se příkladem za důkazem Riceho věty ve skriptech.
- Vysvětlete vlastními slovy důsledky Riceho věty pro testování a ladění počítačových programů, uveďte alespoň 3 příklady (jiné než ve skriptech) v praxi se vyskytujících problémů, jejichž nerozhodnutelnost plyne z Riceho věty.