2016-02-03

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.

Žádné komentáře :

Okomentovat

Dotaz, připomínka, oprava?
(pokud máte problém s vložením příspěvku, vyzkoušejte to v prohlížeči Chrome)