IB102 – úkol 10, příklad 1 – řešení Odevzdání: 14. 12. 2015
Vypracoval(a): UČO:
Skupina:
1. [2 body] Dokažte, že problém určit, zda Turingův stroj M akceptuje nekonečně
mnoho slov, je nerozhodnutelný. Jinými slovy, dokažte, že jazyk
L = { M | L(M) je nekonečný}
není rekursivní.
Návod: Ukažte, že platí vztah N ≤m L, kde N je vhodný nerekursivní jazyk. Zdůvodněte,
proč tudíž jazyk L nemůže být rekursivní.
Důkaz. Ukážeme, že existuje totálně vyčíslitelná funkce f, pro kterou platí:
w ∈ ACC ⇔ f(w) ∈ L
Z existence této funkce pak plyne, že ACC ≤m L, a protože ACC není rekursivní, nemůže
být rekursivní ani L.
Označme Σ abecedu jazyka ACC a Φ abecedu jazyka L. Potom definujeme funkci
f : Σ∗
→ Φ∗
pro každé w ∈ Σ∗
následujícím předpisem.
f(w) =
Trej , jestliže w není kódem žádné dvojice skládající se z TM a slova,
TM,u , jestliže w = M, u pro nějaký TM M a nějaké slovo u,
kde Trej je Turingův stroj, který zamítá každý vstup, a TM,u je Turingův stroj, který
nezávisle na vstupu simuluje výpočet M nad slovem u. Pokud simulace M nad slovem
u skončí v akceptujícím stavu, stroj TM,u akceptuje. Chování TM,u pro libovolný vstup v
můžeme popsat následovně:
1. smaž vstup v,
2. zapiš na pásku u,
3. simuluj Turingův stroj M se vstupem u,
4. pokud stroj M přejde do akceptujícího stavu, přejdi do akceptujícího stavu, pokud
přejde do zamítacího stavu, přejdi do zamítacího stavu.
Funkce f je jistě totální. Zdůvodníme, že je také vyčíslitelná. Na Turingově stroji je možné
rozpoznat, kdy je vstupní slovo kódem dvojice skládající se z Turingova stroje a slova.
V případě, že není, může hledaný Turingův stroj napsat na pásku Trej, což je konstanta,
a skončit. I druhý případ, kdy vstupem je dvojice, je možné realizovat na Turingově
stroji, výpočet kódu stroje TM,u je totiž algoritmicky řešitelný problém. Tudíž funkce f
je vyčíslitelná.
Ukážeme, že funkce f je navíc redukce ACC na L, důkazem obou implikací v definici
redukce.
„⇒“: Předpokládejme nejprve, že platí w ∈ ACC, potom jistě w = M, u pro nějaký
TM M a nějaké slovo u, a navíc TM M akceptuje slovo u. Tudíž podle definice funkce
IB102 – úkol 10, příklad 1 – řešení Odevzdání: 14. 12. 2015
Vypracoval(a): UČO:
Skupina:
f platí f(w) = TM,u . Turingův stroj TM,u akceptuje všechna slova, protože v kroku 3
simulace skončí a následně v kroku 4 stroj TM,u akceptuje, protože M akceptoval. Tedy
platí L(TM,u) = Ψ∗
, kde Ψ je vstupní abeceda stroje TM,u, a proto je jazyk L(TM,u)
nekonečný1
. Z čehož plyne, že f(w) = TM,u ∈ L.
„⇐“: Obměnou, předpokládáme tedy, že w ∈ ACC. Pak můžou nastat dva případy.
1. Slovo w není kódem žádné dvojice skládající se z Turingova stroje a slova. Pak
f(w) = Trej a f(w) ∈ L, protože stroj Trej akceptuje prázdný, a tudíž i konečný,
jazyk.
2. Platí w = M, u pro nějaký TM M a nějaké slovo u a TS M neakceptuje slovo u.
Pak podle definice funkce f platí f(w) = TM,u . Stroj TM,u pak neakceptuje žádné
slovo, protože v kroku 3 zamítá nebo v simulaci cyklí. A tedy f(w) ∈ L.
Nalezli jsme redukci ACC ≤m L, a tedy jazyk L není rekursivní.
1
V případě, že Ψ = ∅, kde Ψ je vstupní abeceda stroje M, pak |Ψ∗
| = 1, což je konečný jazyk. Jestliže
M, u ∈ ACC, pak ale TM,u musí akceptovat nekonečný jazyk, proto musíme rozšířit vstupní abecedu
stroje TM,u o libovolný nový znak, abychom umožnili nekonečný počet vstupů.