Turingovy stroje

Turing machine

M = (Q, Σ, Γ, δ, q₀, q_F)

• Q – konečná množina stavů
• Σ – konečná vstupní abeceda, Δ ∉ Σ
• Γ – konečná pásková abeceda, Σ ⊂ Γ, Δ ∈ Γ
• δ – parciální přechodová funkce, δ: (Q \ {q_F}) × Γ → Q × (Γ ∪ {L, R}), kde L, R ∉ Γ
• q₀ – počáteční stav, q₀ ∈ Q
• q_F – koncový stav, q_F ∈ Q

Jestli má stroj více pásek, nebo je nedeterministický nijak nezvětšuje jeho schopnost přijímat jazyky!

Množina všech řetězců v obsahu pásky ve vstupní konfiguraci pro které TS normálně zastaví.

• Úplný Turingův stroj¹⁾ ⇔ 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

Úplný TS vždy zastaví.

TS s omezenou páskou. Přijímá kontextové jazyky.

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.