-
Church-Turingova teze
Turingovy stroje definují svou výpočetní silou to, co považujeme za efektivně vyčíslitelné
-
Turingův stroj
- M = (Q, Σ, Γ, δ, q0, qF)
- Q konečná množina stavů
- Σ konečná vstupní abeceda, Δ ∉ Σ
- Γ konečná pásková abeceda, Σ ⊂ Γ, Δ ∈ Γ
- δ: (Q{qF})×Γ → Q×(Γ∪{L, R}) parciální přechodová funkce
- q0 počáteční stav
- qF koncový stav
-
Vícepáskový TS
- M = (Q, Σ, Γ1, ..., Γk, δ, q0, qF)
- δ: (Q{qF})×Γ1×...×Γk → Q×(∪{i}×(Γi∪{L, R}))
- čte symboly ze všech pásek, posouvá se/zapisuje jenom na jedné
-
Nedeterministický TS
δ: (Q{qF})×Γ → 2Q×(Γ∪{L, R})
-
Ekvivalence TS a NTS
- důkaz - 3 pásky:
- 1. vstupní řetězec
- 2. kopie vstupního řetězce
- 3. pomocná, sekvence přechodů
-
Konfigurace TS
- konfigurace pásky: {γΔω | γ ∈ Γ*}×N (obsah pásky + pozice hlavy)
- Δω: množina všech nekonečných řetězců nad Δ
- konfigurace stroje: ∈ Q×{γΔω | γ ∈ Γ*}×N
-
Přechod TS
- substituce: sbn(γ) nahrazení n-tého symbolu řetězce γ symbolem b
- zápis: (q1, γ, n) ⊢M (q2, sbn(γ), n) ⇔ δ(q1, γn) = (q2, b)
- posun doprava: (q1, γ, n) ⊢M (q2, γ, n+1) ⇔ δ(q1, γn) = (q2, R)
- posun doleva: (q1, γ, n) ⊢M (q2, γ, n-1) ⇔ δ(q1, γn) = (q2, L) ∧ n > 0
-
Výpočet TS
- posloupnost konfigurací K0, K1, ...
- Ki ⊢M Ki+1
- buď nekonečná, nebo konečná (normální/abnormální zastavení - q = qF/nedefinovaný přechod nebo posun mimo pásku)
-
Další varianty TS
- více koncových stavů
- dva koncové stavy (úspěch/neúspěch)
- zarážka na konci pásky
- přepis a posuv v jedné operaci
-
-
Jazyk přijímaný TS
- w ∈ Σ* je přijat TS ⇔
- (q0, ΔwΔω, 0) ⊢M* (qF, γ, n), γ ∈ Γ*, n ∈ N
- L(M) = {w | w je přijat TS M}
-
Úplný TS
pro každý vstup zastaví
-
Univerzální TS
- TU
- jako vstup přijímá kód jiného TS a vstupní slovo stroje
- dokáže rozkódovat přechodovou funkci stroje a výpočet tohoto stroje simulovat
- dokáže vypočítat libovolnou částečně rekurzivní funkci
- rozhoduje jakýkoliv rekurzivní jazyk
- přijímá libovolný rekurzivně spočetný jazyk
-
Lineárně omezený TS
- LOA, nedeterministický TS, který nikdy neopustí tu část pásky, na níž je zapsán jeho vstup
- není známo, zda je DLOA je striktně slabší než LOA
|
|
