IB102 – úkol 10, příklad 1 – řešení Odevzdání: 8. 12. 2014
Vypracoval(a): UČO:
Skupina:
1. [2 body] Dokažte, že problém určit, zda funkce popsaná zadaným Turingovým strojem
M má v oboru hodnot řetězec „redukce“, je nerozhodnutelný. Jinými slovy, dokažte, že
jazyk
L = { M | existuje slovo w, pro které platí M(w) = redukce}
není rekurzivní.
Návod: Ukažte, že platí vztah HALT ≤m L, a zdůvodněte, proč tudíž jazyk L nemůže
být rekurzivní.
Důkaz. Ukážeme, že existuje totálně vyčíslitelná funkce f, pro kterou platí:
w ∈ HALT ⇔ f(w) ∈ L
Z existence této funkce pak plyne, že HALT ≤m L a protože HALT není rekurzivní,
nemůže být rekurzivní ani L.
Označme Σ abecedu jazyka HALT a Φ abecedu jazyka L. Potom definujeme funkci
f : Σ∗
→ Φ∗
pro každé w ∈ Σ∗
následujícím předpisem.
f(w) =
Tinf , jestliže w není kódem žádné dvojice skládající se z TS a slova,
TM,u , jestliže w = M, u pro nějaký TS M a nějaké slovo u,
kde Tinf je Turingův stroj, který cyklí nad každým vstupem a TM,u je Turingův stroj, který
nezávisle na vstupu simuluje výpočet M nad slovem u. Pokud simulace skončí (výpočet
nad slovem u je konečný) TM,u zapíše se na výstup slovo redukce a akceptuje. Chování
TM,u pro libovolný vstup v můžeme popsat následovně:
1. Smaž vstup v.
2. Zapiš na vstup u.
3. Simuluj Turingův stroj M se vstupem u.
4. Zapiš na výstup slovo redukce.
5. Akceptuj.
Konstrukci Tinf zvládneme jednoduše, jelikož pro nekorektní vstup w může funkce f vracet
konstantu – TS který cyklí. Máme-li vstup tvaru M, u pak pro něj dokážeme algoritmicky
zkonstruovat TM,u, který provádí výše uvedený algoritmus, tedy podle ChurchovyTuringovy
teze existuje Turingův stroj, který tento algoritmus realizuje, a tedy funkce f
je totálně vyčíslitelná. Ukážeme, že funkce f je navíc redukce HALT na L, důkazem obou
implikací v definici redukce.
„⇒“: Předpokládejme nejprve, že platí w ∈ HALT, potom jistě w = M, u pro
nějaký TS M a nějaké slovo u a navíc výpočet TS M nad slovem u je konečný. Pak podle
definice platí f(w) = TM,u . Výpočet TM,u nad libovolným slovem v vrátí slovo redukce,
protože v kroku 3 simulace skončí, v kroku 4 zapíše na výstup slovo redukce a následně v
IB102 – úkol 10, příklad 1 – řešení Odevzdání: 8. 12. 2014
Vypracoval(a): UČO:
Skupina:
kroku 5 slovo v akceptuje. Tedy existuje slovo x (dokonce to platí pro každé slovo), pro
nějž platí TM,u(x) = redukce a tedy f(w) = TM,u ∈ L.
„⇐“: Obměnou, předpokládáme tedy, že w ∈ HALT. 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) = Tinf a f(w) ∈ L, protože stroj Tinf cyklí nad každým slovem a tedy nevrátí
žádný výstup.
2. Platí w = M, u pro nějaký TS M a nějaké slovo u a navíc výpočet TS M nad
slovem u není konečný. Pak podle definice platí f(w) = TM,u . Výpočet TM,u nad
každým slovem je pak nekonečný, protože v kroku 3 simulace cyklí. A tedy f(w) ∈ L.
Nalezli jsme redukci HALT ≤m L, a tedy jazyk L není rekursivní.