Turingovy stroje

Turing machine

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

Q – konečná množina stavů

Σ – konečná vstupní abeceda, Δ ∉ Σ

Γ – konečná pásková abeceda, Σ ⊂ Γ, Δ ∈ Γ

δ – parciální přechodová funkce, δ: (Q \ {qF}) × Γ → Q × (Γ ∪ {L, R}), kde L, R ∉ Γ

q₀ – počáteční stav, q₀ ∈ Q

qF – koncový stav, qF ∈ 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 stroj1) 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.