====== Turingovy stroje  ======
[[wp>Turing machine]]

//M// = (//Q//, //Σ//, //Γ//, //δ//, //q//₀, //q<sub>F</sub>//)
  * //Q// -- konečná množina stavů
  * //Σ// -- konečná vstupní abeceda, //Δ// ∉ //Σ//
  * //Γ// -- konečná pásková abeceda, //Σ// ⊂ //Γ//, //Δ// ∈ //Γ//
  * //δ// -- parciální přechodová funkce, //δ//: (//Q// \ {//q<sub>F</sub>//}) × //Γ// → //Q// × (//Γ// ∪ {//L//, //R//}), kde //L//, //R// ∉ //Γ//
  * //q//₀ -- počáteční stav, //q//₀ ∈ //Q//
  * //q<sub>F</sub>// -- koncový stav, //q<sub>F</sub>// ∈ //Q//

Jestli má stroj více pásek, nebo je nedeterministický nijak nezvětšuje jeho schopnost přijímat jazyky!
===== Jazyky přijímané TS =====
Množina všech řetězců v obsahu pásky ve vstupní konfiguraci pro které TS normálně zastaví.

  * Úplný Turingův stroj((vždy zastaví)) ⇔ rekurzivní jazyk
  * Turingův stroj ⇔ rekurzivně vyčíslitelný jazyk

Speciálním případem TS jsou linárně omezené automaty (LOA), je to vlastně TS ale s konečnou páskou, a dokáží přijímat kontextové jazyky
===== Varianty TS =====
**Úplný TS** vždy zastaví.
==== Lineárně omezené automaty ====
TS s omezenou páskou. Přijímá kontextové jazyky.
==== Univerzální TS ====
Umí interpretovat jiné TS. Na vstupu se nějak (pomocí ''1'', ''0'' a speciálních symbolů) zakódují pravidla TS a obsah pásky.