IB102 – úkol 10, příklad 1 – řešení Odevzdání: 9. 12. 2013
Vypracoval(a): UČO:
Skupina:
1. [2 body] Dokažte, že následující jazyk není rekurzivní pomocí redukce z vhodného
nerekurzivního jazyka.
L = {<M> | |L(M)| = 1}
Tedy L je jazykem všech kódů Turingových strojů, které akceptují právě jedno slovo.
Dokážeme, že jazyk ACC (jazyk reprezentující problém akceptování uvedený na přednášce)
se redukuje na jazyk L, tedy ACC ≤m L.
Důkaz. Ukážeme, že existuje totálně vyčíslitelná funkce f, pro kterou platí: x ∈ ACC ⇔
f(x) ∈ L. Z existence této funkce pak plyne, že ACC ≤m L a protože ACC není rekurzivní,
nemůže být rekurzivní ani L.
Sestrojíme funkci f, která pro každé x vrátí kód TM M , který bude akceptovat slovo
ε, jestliže x ∈ ACC, žádné slovo jinak. Toho docílíme tak, že M nejprve zkontroluje,
jestli je x tvaru <M, w>, a poté simuluje stroj M na slově w. Skončí-li výpočet úspěšně,
podívá se teprve na svůj vlastní vstup a akceptuje, jestliže má na vstupu ε.
Definujeme tedy funkci f pro každé x předpisem
f(x) = <M >,
kde M je Turingův stroj, který se chová na vstupu y následovně:
• není-li y tvaru <M, w>, zamítni
• spusť U na <M>#<w> (U je univerzální TM, viz přednáška)
• pokud U přejde do akceptujícího stavu a
– y = ε, akceptuj
– y = ε, zamítni
• pokud U přejde do zamítajícího stavu, zamítni
Funkce f splňuje x ∈ ACC ⇔ f(x) ∈ L.
• x ∈ ACC ⇒ f(x) ∈ L
– x není tvaru <M, w>
Pak x /∈ ACC a implikace triviálně platí.
– x je tvaru <M, w>
Jestliže <M, w> ∈ ACC, pak TS M akceptuje w, a tedy i univerzální TM
U akceptuje <M>#<w>, a M proto akceptuje jediné slovo (ε) ⇒ <M > ∈
L ⇒ f(x) ∈ L.
• f(x) ∈ L ⇒ x ∈ ACC
Ukážeme obměnou (x /∈ ACC ⇒ f(x) /∈ L).
Jestliže x /∈ ACC, pak buď
1
IB102 – úkol 10, příklad 1 – řešení Odevzdání: 9. 12. 2013
Vypracoval(a): UČO:
Skupina:
– x není tvaru <M, w> a M zamítá (nehledě na vstup) ⇒ <M > /∈ L ⇒
f(x) /∈ L .
– x je tvaru <M, w>, ale M neakceptuje w (nebo na něm cyklí), pak ani U
neakceptuje (nebo cyklí), a tedy M neakceptuje žádné slovo ⇒ <M > /∈
L ⇒ f(x) /∈ L.
Zbývá ukázat, že funkce f je totálně vyčíslitelná. Výše popsaný postup nám dává
algoritmus konstrukce M na základě vstupu y, tedy podle Church-Turingovy teze existuje
TM, který tento algoritmus realizuje, a tedy funkce f je vyčíslitelná.
Že je funkce totální vidíme přímo z jejího předpisu (je definována pro každé x a vždy
vrátí odpovídající M ).
Dokázali jsme tedy, že ACC ≤m L a protože ACC není rekursivní jazyk, nemůže být
ani jazyk L rekursivní.
2