Vyčíslitelnost a složitost výpočtů

Rozhodnutelné a nerozhodnutelné problémy, metoda diagonalizace

Shrnutí kapitoly

Rozhodovací problém je množina otázek (případů) s odpověďmi ANO/NE. Každý rozhodovací problém se dá popsat (charakterizovat) nějakým formálním jazykem. Tento jazyk obsahuje popisy všech případů problému s odpovědí ANO.

Jazyk je rekurzívně spočetný, je-li přijímán nějakým Turingovým strojem (takových strojů může být více). Pokud existuje Turingův stroj, který jazyk přijímá a který se zastaví pro jakýkoli vstup (i tehdy, když nedojde do koncového stavu), nazývá se jazyk rekurzívní. Každý rekurzívní jazyk je i rekurzívně spočetný, obráceně to platit nemusí.

Intuitivně nazveme problém rozhodnutelným, jestliže existuje algoritmus, který umí správně zodpovědět (rozhodnout) každý jeho případ. To je ekvivalentní požadavku, aby jazyk charakterizující problém byl rekurzívní. Proto je pro nás důležité studovat vlastnosti rekurzívních a rekurzívně spočetných jazyků.

Existují jazyky, které nejsou rekurzívně spočetné, dokonce je jich velké množství. Existence aspoň jednoho takového jazyka označeného , který není akceptován žádným Turingovým strojem, se dá dokázat sporem, tzv. diagonalizační metodou. Název metody vychází z použití rovinného grafu s dvěma kolmými osami.  Na jednu osu umístíme všechny Turingovy stroje a na druhou osu jejich vstupní slova. Budeme (mylně) předpokládat, že existuje Turingův stroj přijímající class= a na diagonále (úhlopříčce) grafu dojdeme k logickému paradoxu, čili sporu. Tím je předpoklad vyvrácen, tedy jazyk  class= skutečně není rekurzívně spočetný.

Studijní materiál

Skripta P. Sosík, Teorie vyčíslitelnosti, kapitola 3, od začátku až po část 3.2 včetně.

Příklady a problémy
  1. Ukažte, že třída rekurzívních jazyků je uzavřená na sjednocení, průnik a doplněk. Jinými slovy, jestliže L_1 a L_2 jsou rekurzívní jazyky, pak i L_1\cup L_2 , L_1\cap L_2 a \overline{L_1} jsou rekurzívní.

    • Návod: jsou-li jazyky  L_1 a L_2 rekurzívní, pak existují Turingovy stroje  M1 a M2, které je přijímají. Jejich úpravou, resp. kombinací získáme takové TS, které budou přijímat sjednocení, průnik a doplněk těchto  jazyků. V případě doplňku je situace nejjednodušší. Pro TS  M1 stačí prohodit stavy qaccept a qreject a získáme stroj, který zamítne všechna slova z jazyka  L_1 a přijme ta, která do něj nepatří, čili doplněk. V případě sjednocení sestrojíme TS, který paralelně simuluje běh M1 a M2 . Jestliže alespoň jeden skončí pro dané slovo v akceptujícím stavu, pak slovo náleží do sjednocení. Pro průnik obdobně sestrojíme TS který paralelně simuluje běh  M1 a M2. Jestliže oba skončí pro dané slovo v akceptujícím stavu, pak slovo náleží do průniku. Řešením příkladu je podrobně popsat, jak se tyto stroje sestrojí.

  2. Uveďte příklad a) alespoň dvou rekurzivních jazyků, b) jazyka, který je rekurzivně spočetný, ale není rekurzivní, c) jazyka, který není rekurzivně spočetný.

    • Návod:  lze použít jazyky popsané ve skriptech.
Zde odevzdejte řešení příkladu 1 výše
Předchozí
Následující