Turingův stroj

Definice: Turingův stroj je $T=(Q,\Sigma ,\Gamma ,\delta ,q_0,B,F)$, kde

• $Q$ je množina stavů,
• $\Sigma$ je množina vstupních symbolů,
• $\Gamma \supseteq \Sigma$ je množina symbolů pásky, $Q\cap \Gamma =\varnothing$,
• $\delta :(Q\setminus F)\times \Gamma \to Q\times \Gamma \times \{L,R\}$ je přechodvá funkce,
• $q_0\in Q$ je počáteční stav,
• $B\in \Gamma \setminus \Sigma$ je symbol pro prázdnou buňku,
• $F\subseteq Q$ jsou přijímající stavy. Jazyky přijímané Turingovými stroji jsou rekurzivně spočetné jazyky, odpovídající gramatikám typu 0.

---

Algoritmicky nerozhodnutelné problémy

Definice: Rozhodnutelný problém je množina vstupů na které existuje odpověď ANO/NE.

Definice: Problém je algoritmicky rozhodnutelný pokud existuje Turingův stroj takový, že pro každý vstup zastaví a přijme právě když odpovědí na problém formulovaný vstupem je ANO.

Problémy na sebe můžeme redukovat obdobně jako v kapitole Třídy složitosti.

Tvrzení: Problém zastavení je nerozhodnutelný. Definice: Instancí problému je dvojice $M,w$, Turingův stroj a jeho vstup a chceme rozhodnou, zda existuje algoritmus $Halt(M,w)$, který vydá $1$ právě když $M$ zastaví na vstupu $w$.

Důkaz: Redukujeme $Halt(M,w)$ na $L_d$, tedy diagonální jazyk.

Diagonální jazyk $L_d$ je jazyk $w\in \{0,1{\}}^{\ast }$, takový že Turingův stroj reprezentovaný slovem $w$ nepřijímá slovo $w$. Předpokládejme $L_d=L(M_d)$, pak si vyrobíme tabulku, kde se ptáme “Přijímá $M_i$ vstupní slovo $w_j$” (od toho diagonála) a mějme tedy $w_d$ a $M_d$. Je $w_d\in L_d$?

• Pokud ano, tak $M_d$ nemá přijímat $w_d$ a tedy není součástí jazyka $L_d⟹$ spor.
• Pokud ne, tak $M_d$ přijímá $w_d$ a tedy patří do $L_d⟹$ spor.

Teď k redukci, předpokládejme že máme algoritmus na $Halt$, modifikujeme ho na $Hal{t}_{no}(w),w\in \{0,1{\}}^{\ast }$, tedy odpovídáme na to zda $M$ nepřijímá slovo $w$, pak $Halt(Hal{t}_{no}(w),Hal{t}_{no}(w))$ je ekvivalentní diagonálnímu jazyku a tedy je to nespočetné.