Turingův stroj



Turingův stroj
•Proč Turingův stroj:
•Nejjednodušší univerzální matematický model počítače.
•Snadno se zkoumají jeho vlastnosti.
•I přes jednoduchost umí spočítat totéž co dnešní počítače.
•Umožňuje zkoumat výpočetní limity:
•Vyčíslitelnost – co lze a nelze spočítat.
•Složitost – jak efektivně to lze spočítat.
•Dominantní model oproti jiným (RAM stroje).
•

Turingův stroj
•Turingův stroj je uspořádaná šestice:
•M = (Q, Σ, Γ, δ, q₀, F)
•Q – konečná neprázdná množina stavů
•Σ – vstupní abeceda (Σ ⊆ Γ)
•Γ – pásková abeceda (symboly na pásce)
•q₀ ∈ Q – počáteční stav
•F ⊆ Q – množina koncových stavů
•δ – přechodová funkce
•δ : Q × Γ → Q × Γ × {−1, 0, 1}
•δ(qᵢ, a) = (qⱼ, b, P), kde:
•qᵢ, qⱼ ∈ Q (stav)
•a, b ∈ Γ (symbol na pásce)
•P ∈ {−1, 0, 1} (pohyb: doleva, bez posunu, doprava)
•

Turingův stroj
•Jde o snadno pochopitelný model skutečného počítače s páskovou pamětí
•Lehce programovatelný
•Má nekonečnou pásku, na níž jsou zapsány symboly.
•Hlava dokáže symbol přečíst, přepsat a posunout se doleva nebo doprava.
•Výpočet začíná v počátečním stavu a končí v koncovém stavu.
•

Alan Turing
•Britský matematik, logik a kryptanalytik
•„Otec moderní informatiky“
•Během 2. světové války se podílel na prolomení šifry Enigma
•Jeho práce položila základy teorie vyčíslitelnosti, složitosti a umělé inteligence
•

Turingův stroj
•Základní vlastnosti Turingova stroje
•Jednoduchost – má jen pásku, hlavu a sadu stavů
•Univerzálnost – dokáže simulovat jakýkoliv algoritmus
•Determinističnost – pro daný stav a symbol je vždy určeno, co se má stát
•Neomezená paměť – páska je teoreticky nekonečná
•Zastavení – výpočet končí, když stroj vstoupí do koncového stavu
•Základní model výpočtu – hranice toho, co lze spočítat
•

Turingův stroj
•Základní principy Turingova stroje:
•Páska: Nekonečně dlouhá páska rozdělená na jednotlivé buňky, kde každá buňka může obsahovat symbol
(např. 0 nebo 1) nebo může být prázdná. Páska slouží jako paměť stroje.
•Hlava: Pohyblivá čtecí a zapisovací hlava, která se může pohybovat doleva nebo doprava po pásce.
Hlava může číst symboly z pásky, přepisovat je a provádět určité akce na základě stavu stroje.
•Stavy: Turingův stroj má konečný počet stavů, ve kterých se může nacházet. Každý stav představuje
aktuální konfiguraci stroje.
•Přechodová funkce: Určuje, jak se Turingův stroj chová v závislosti na aktuálním stavu a symbolu,
který právě čte. Na základě této funkce může stroj provést několik akcí: změnit symbol na pásce,
posunout hlavu doleva nebo doprava a přejít do jiného stavu.

Turingův stroj
Editor Turingovych stroju


Turingův stroj
•Deterministický Turingův stroj (DTM)
• Pro každý stav a symbol existuje právě jedno přechodové pravidlo
•Nedeterministický Turingův stroj (NTM)
•Pro stav a symbol může existovat více pravidel → stroj si „vybere cestu“
•Vícepáskový
•Máme více pásek, každá má vlastní čtecí a zápisovou hlavu, tyto hlavy se mohou pohybovat navzájem
nezávisle.
•

Turingův stroj
•Navrhněte TS, který sečte dvě čísla v unární soustavě.


Turingův stroj
•Řešení:
•TS= (Q, Σ, Γ, δ, q0, F)
•Q = {q0, q1, q2}
•Σ = {1, 0}
•Γ = {1, 0, _}
•Počáteční stav: q0
•Konečný stav: q2
•
•
•Přechodové stavy:
•δ(q0, 1) = (1, R, q0)
•δ(q0, 0) = (1, R, q1)
•δ(q1, 1) = (1, R, q1)
•δ(q1, _) = (_, L, q1)
•δ(q1, 1) = (_, S, q2)

Turingův stroj
•Turingův stroj pro jazyk L = {anbncn | n ≥ 0}


Turingův stroj
•Řešení:
•TS= (Q, Σ, Γ, δ, q0, F)
•Q = {q0, q1, q2, q3, q4, qacc, qrej}
•Σ = {a, b, c}
•Γ = {_, a, b, c, x}
•Počáteční stav: q0
•Konečné stavy: {qacc, qrej}
•

Turingův stroj
•Stav q0
•δ(q0, _) = (qacc, _, S)
•δ(q0, a) = (q1, x, R)
•δ(q0, b) = (qrej, b, S)
•δ(q0, c) = (qrej, c, S)
•δ(q0, x) = (q0, x, R)
•Stav q1
•δ(q1,_) = (qrej, _, S)
•δ(q1, a) = (q1, a, R)
•δ(q1, b) = (q2, x, R)
•δ(q1, c) = (qrej, c, S)
•δ(q1, x) = (q1, x, R)
•Stav q2
•δ(q2, _) = (qrej, _, S)
•δ(q2, a) = (qrej, a, S)
•δ(q2, b) = (q2, b, R)
•
•δ(q2, c) = (q3, x, R)
•δ(q2, x) = (q2, x, R)
•Stav q3
•δ(q3, _) = (q4, _, L)
•δ(q3, a) = (qrej, a, S)
•δ(q3, b) = (qrej, b, S)
•δ(q3, c) = (q3, c, R)
•δ(q3, x) = (q3, x, R)
•Stav q4
•δ(q4, _) = (q0, _, R)
•δ(q4, a) = (q4, a, L)
•δ(q4, b) = (q4, b, L)
•δ(q4, c) = (q4, c, L)
•δ(q4, x) = (q4, x, L)
•

Church–Turingova teze
•Cokoliv, co lze efektivně vypočítat pomocí algoritmu, lze vypočítat i na Turingově stroji.
•Formulována Alonzem Churchem (lambda kalkul) a Alanem Turingem (Turingův stroj)
•Jinými slovy: Turingův stroj je univerzální model výpočtu
•Teze není matematická věta (nelze ji dokázat), ale obecně přijímaný princip informatiky.
•
•

Church–Turingova teze
•Důsledky:
•Teze vymezuje hranici výpočtů:
•Pokud něco nejde spočítat na Turingově stroji, pak to nejde spočítat žádným algoritmem.
•Proto je Turingův stroj používán jako standardní model v teorii vyčíslitelnosti.

Úkol
•Navrhněte TS, který přijímá jazyk L = {ww | w ∈ {a, b, c}* }.
•Nápověda: použijte více pásek