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é.