Skip to content

6.2 Turingovy stroje

Definici (ne)deterministického Turingova stroje jsme si již uvedli v předchozí kapitole.

Ekvivalence DTS a NTS

Nedeterministický a deterministický Turingův stroj jsou výpočetně ekvivalentní.

Oba přijímají právě množinu rekurzivně spočetných jazyků. DTS je speciálním případem NTS a každý NTS lze převést na DTS.

Definice (Vícepáskový Turingův stroj)

Vícepáskový Turingův stroj

Vícepáskový Turingův stroj je Turingův stroj s více páskami a více nezávislými čtecími hlavami.

  • Jednopáskový TS je speciálním případem vícepáskového TS.
  • Každý vícepáskový TS lze převést na jednopáskový.
  • Oba typy jsou výpočetně ekvivalentní.

Vícepáskový stroj Vícepáskový stroj

Definice (Univerzální Turingův stroj)

Univerzální Turingův stroj

Uvažujme kódování Turingova stroje (zakódování jeho přechodové funkce do řetězce nul a jedniček).

Univerzální Turingův stroj \(R_U\) je takový stroj, který:

  1. Na vstupu dostane libovolný zakódovaný Turingův stroj \(R\) a řetězec \(w\).
  2. Simuluje výpočet Turingova stroje \(R\) nad řetězcem \(w\).

\(R_U\) přijme vstup právě tehdy, když \(R\) přijme \(w\). Pokud se \(R\) zacyklí, zacyklí se i \(R_U\). Jazyk přijímaný tímto strojem nazýváme univerzální jazyk \(L_U\).