TIN 17. Turingovy stroje

Card Set Information

Author:
hrbi
ID:
222666
Filename:
TIN 17. Turingovy stroje
Updated:
2013-06-16 05:10:34
Tags:
tin
Folders:

Description:
mssz 2013
Show Answers:

Home > Flashcards > Print Preview

The flashcards below were created by user hrbi on FreezingBlue Flashcards. What would you like to do?


  1. Church-Turingova teze
    Turingovy stroje definují svou výpočetní silou to, co považujeme za efektivně vyčíslitelné
  2. 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
  3. 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é
  4. Nedeterministický TS
    δ: (Q{qF})×Γ → 2Q×(Γ∪{L, R})
  5. Ekvivalence TS a NTS
    • důkaz - 3 pásky:
    • 1. vstupní řetězec
    • 2. kopie vstupního řetězce
    • 3. pomocná, sekvence přechodů
  6. 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
  7. 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
  8. Výpočet TS
    • posloupnost konfigurací K0, K1, ...
    • KiM Ki+1
    • buď nekonečná, nebo konečná (normální/abnormální zastavení - q = qF/nedefinovaný přechod nebo posun mimo pásku)
  9. 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
  10. Modulární konstrukce TS
    • spojování jednodušších TS ve složitější celek
    • kresleno pomocí kompozitních diagramů
    • nepodmíněné předání řízení:
    • podmíněné předání řízení:
    • parametrová konvence:
    • při neexistenci přechodu TS přejde do koncového stavu - tj. přijme!

    • Základní stavební bloky TS
    • posun doleva (L), posun doprava (R), na aktuální pozici zapiš x (x)
    • posun doleva, až narazíš na x (L<sub>x</sub>), anal. doprava (R<sub>x</sub>)
    • posun obsahu pásky doleva (S<sub>L</sub>) a doprava (S<sub>R</sub>)
  11. 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}
  12. Úplný TS
    pro každý vstup zastaví
  13. 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
  14. 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

What would you like to do?

Home > Flashcards > Print Preview