Definice: Turingův stroj je , kde
- je množina stavů,
- je množina vstupních symbolů,
- je množina symbolů pásky, ,
- je přechodvá funkce,
- je počáteční stav,
- je symbol pro prázdnou buňku,
- 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 , Turingův stroj a jeho vstup a chceme rozhodnou, zda existuje algoritmus , který vydá právě když zastaví na vstupu .
Důkaz: Redukujeme na , tedy diagonální jazyk.
Diagonální jazyk je jazyk , takový že Turingův stroj reprezentovaný slovem nepřijímá slovo . Předpokládejme , pak si vyrobíme tabulku, kde se ptáme “Přijímá vstupní slovo ” (od toho diagonála) a mějme tedy a . Je ?
- Pokud ano, tak nemá přijímat a tedy není součástí jazyka spor.
- Pokud ne, tak přijímá a tedy patří do spor.
Teď k redukci, předpokládejme že máme algoritmus na , modifikujeme ho na , tedy odpovídáme na to zda nepřijímá slovo , pak je ekvivalentní diagonálnímu jazyku a tedy je to nespočetné.