Turingův stroj - syntaxe
Definice. (Deterministický) Turingův stroj (Turing Machine, TM) je
devítice M = (Q, Z, r, >, u, S, cfo, Qacc, Qrej), kde
■ Q je konečná množina, jejíž prvky nazýváme stavy,
■ Z je konečná množina, tzv. vstupní abeceda,
■ r je konečná množina, tzv. pracovní abeceda, Z c r,
■ > g r \ Z je levá koncová značka,
■ u g r \ Z je symbol označující prázdné políčko,
■ ô : (Q \ {qacc, qrej}) x T -> Oxľx{L,fi}
je totální přechodová funkce,
■ Qo e Q je počáteční stav,
■ Qacc ^ Q je akceptující stav,
■ qrej g Q je zamítající stav.
IB102 Automaty, gramatiky a složitost, 23.11.2015 1/31
Dále požadujeme, aby pro každé q e Q existoval p e Q takový, že
S(q, >) = (p, >, R) (tj. > nelze přepsat ani posunout hlavu za okraj pásky).
Označení- uw = uuuuuu...
Definice. Konfigurace Turingova stroje je trojice
(q, z, n) g Q x {yuu \ y e r*} x N0, kde
■ q je stav,
■ yuu je obsah pásky,
■ n značí pozici hlavy na pásce.
Počáteční konfigurace pro vstup w e Z* je trojice (g0, >wuu, 0). Akceptující konfigurace je každá trojice tvaru (gacc, z, n). Zamítající konfigurace je každá trojice tvaru {qrej, z, rí).
IB102 Automaty, gramatiky a složitost, 23.11.2015
2/31
Výpočet Turingova stroje
Označení. Pro libovolný nekonečný řetěz z nad I", zn označuje n-tý symbol řetězu z (z0 je nejlevější symbol řetězu z). Dále s£(z) označuje řetěz vzniklý ze z nahrazením zn symbolem b.
Definice. Na množině všech konfigurací stroje M definujeme binární
relaci krok výpočtu
M
takto:
(P, z, n)
M
<
(q, sg(z), n + 1) pro č(p, zn) = (g, to, R) ^ (g, sg(z), n - 1)    pro č(p, zn) = (g, b, L)
IB102 Automaty, gramatiky a složitost, 23.11.2015
3/31
Výpočet TM M na vstupu w je maximálni (konečná nebo nekonečná) posloupnost konfigurací K0,   , K2,..kde K0 je počáteční konfigurace
pro w a Kj pro všechna / > 0.
Stroj M akceptuje slovo w právě když výpočet M na w je konečný a jeho poslední konfigurace je akceptující.
Stroj M zamítá slovo w právě když výpočet M na w je konečný a jeho poslední konfigurace je zamítající.
Stroj M pro vstup w cyklí právě když výpočet M na w je nekonečný.
Jazyk akceptovaný TM .M definujeme jako
L(M) = {i/i/ g 51* | .M akceptuje w}.
IB102 Automaty, gramatiky a složitost, 23.11.2015
4/31
Ukázky Turingových strojů
Simulátor TM:
http://www.fi.muni.cz/~xbarnat/taf j/turing/
Různé úrovně popisu TM
■ formální
■ neformální implementační
■ vysokourovňový
IB102 Automaty, gramatiky a složitost, 23.11.2015
5/31
Vícepáskový Tu ringů v stroj
Definice, /c-páskový Turingův stroj je definován stejně jako TM
s výjimkou přechodové funkce S, která je definována jako totální funkce
S : (Q x {qacc, qrej}) x Vk -> Q x Vk x {L, R}k.
Konfigurace mají tvar (g,z1,... ,zk, n-i,...,nk) e Qx(r*.{u^})/cxN^. Počáteční konfigurace pro w e 51* je (g0, > wu^, ou",..., ou", 0,..., 0)
Definice akceptující/zamítající konfigurace a her se změní podobně.
M
IB102 Automaty, gramatiky a složitost, 23.11.2015 6/31
Ekvivalence vícepáskového a jednopáskového TM
Věta. Pro každý vícepáskový Turingův stroj existuje ekvivalentní (jednopáskový) TM.
Důkaz.
Neprázdný obsah k pásek a polohy hlav vložíme za sebe na 1 pásku.
Simulace jednoho kroku = zjistit informace pod hlavami, zapsat nové a posunout hlavy.
Je-li třeba další políčko nějaké pásky, posuneme zbývající obsah.
IB102 Automaty, gramatiky a složitost, 23.11.2015
□
7/31
Nedeterministický Turingův stroj
Definice. Nedeterministický Turingův stroj M je definován stejně jako TM s výjimkou přechodové funkce S, která je definována jako totální funkce ô : (Q \ {qacCl qrej}) x r 2°^^R\
Všechny pojmy se definují stejně jako u deterministického TM. Drobné změny jsou jen u definice kroku výpočtu       a akceptace slova.
(p,z,n) hžtr (4,s£(z),n+1) jestliže {q,b, R) e S{p,zn) (p,z,n) ^ (g,sg(z),n-1) jestliže  {q,b, L) e S{p,zn)
M akceptuje slovo w, právě když existuje výpočet z počáteční konfigurace pro w do nějaké akceptující konfigurace.
IB102 Automaty, gramatiky a složitost, 23.11.2015
8/31
Ekvivalence nedeterministického a deterministického TM
Věta. Pro každý nedeterministický Turingův stroj J\í existuje ekvivalentní deterministický TM.
Intuice:
IB102 Automaty, gramatiky a složitost, 23.11.2015
9/31
Důkaz. Sestrojíme 3-páskový deterministický TM prozkoumávající výpočtový strom stroje A/". Tento 3-páskový stroj lze převést na jednopáskový deterministický TM.
Nechť k = max{|£(g,z)| | qe Q \ {qacc, qrey},z e
1. páska obsahuje vždy pouze vstup, nemění se.
2. páska slouží k simulaci nedeterministického stroje.
3. páska obsahuje řetězec {1,..., /c}* určující, který uzel stromu je právě prohledáván. Prohledávání začne uzlem 1.
IB102 Automaty, gramatiky a složitost, 23.11.2015 10/31
Hledáme akceptující konfiguraci ve výpočtovém stromě prohledáním do šířky. Kontrola jednoho uzlu výpočtového stromu:
D Zkopíruj první pásku na druhou.
H Na 2. pásce simuluj Af, nedeterministické volby řeš podle čísel na 3. pásce. Narazíš-li na akceptující stav, akceptuj. V ostatních případech (příslušná volba neexistuje nebo M dojde do zamítajícího stavu nebo došly čísla na 3. pásce) pokračuj dalším krokem.
B Nahraď řetězec na 3. pásce chápaný jako číslo v (k + 1 )-ární soustavě nejbližším vyšším číslem neobsahujícím nuly a začni znovu. □
IB102 Automaty, gramatiky a složitost, 23.11.2015
11/31
Další varianty Turingova stroje
■ Turingův stroj s oddělenou vstupní páskou
■ Turingův stroj s oboustranně nekonečnou páskou
■ stroj se dvěma zásobníky
■ stroj se vstupní páskou a dvěma čítači
■ ...
Všechny tyto varianty mají tutéž vyjadřovací sílu.
IB102 Automaty, gramatiky a složitost, 23.11.2015
12/31
Churchova teze
Churchova (Church-Turingova) teze: Každý proces, který lze intuitivně nazvat algoritmem, se dá realizovat na Turingově stroji.
Další ekvivalentní formalismy:
■ Minského stroje
■ A-kalkul
■ while-programy
IB102 Automaty, gramatiky a složitost, 23.11.2015
13/31
Turingovy stroje a třídy jazyků
Věta. Jazyk /.je rekursivně spočetný (tj. generovaný gramatikou typu 0) <=^> Z. je akceptovaný nějakým Turingovým strojem.
Důkaz. Neuveden. □
Definice. Turingův stroj se vstupní abecedou Z se nazývá úplný, je-li každý jeho výpočet konečný (akceptující nebo zamítající). Jazyk se nazývá rekursivní, pokud je akceptovaný nějakým úplným Turingovým strojem.
Terminologie
■ (Obecný) TM M akceptuje/rozpoznává/přijímá jazyk L(M).
■ Je-li TM M úplný, říkáme, že M rozhoduje jazyk L(M).
IB102 Automaty, gramatiky a složitost, 23.11.2015
14/31
Přehled jazykových tříd
Jazyky	Gramatiky (typ)	Automaty
rekursivně spočetné rekursivní kontextové bezkontextové deterministické CFL regulární	frázové (0) kontextové (1) bezkontextové (2) regulární (3)	Tu ringový stroje úplné Turingovy stroje lineárně ohraničené TM zásobníkové automaty deterministické PDA konečné automaty
Třída na nižším řádku je vždy vlastní podtřídou třídy na vyšším řádku.
IB102 Automaty, gramatiky a složitost, 23.11.2015
15/31
Uzáverové vlastnosti rekursivních a rekursivně spočetných jazyků
Věta. Rekursivně spočetné i rekursivní jazyky jsou uzavřené na sjednocení.
Důkaz.
Nechť L|, Z-2 jsou jazyky akceptované TM M\, M2 s disjunktními množinami stavů. Stroj M akceptující L1 u L2 se nedeterministicky rozhodne, zda na svém vstupu spustí M\ nebo Mz. Pokud spuštěný stroj akceptuje nebo zamítne, stroj M udělá totéž. Pokud M\, M2 byly úplné, je i M úplný. □
IB102 Automaty, gramatiky a složitost, 23.11.2015 16/31
Uzáverové vlastnosti rekursivních a rekursivně spočetných jazyků
Věta. Rekursivně spočetné i rekursivní jazyky jsou uzavřené na průnik. Důkaz.
Nechť Li, Z_2 jsou jazyky akceptované TM M\, M2 s disjunktními množinami stavů. Stroj M akceptující Li n L2 spustí na svém vstupu w nejprve M\ a pokud akceptuje, pak na w spustí i Mz- M akceptuje jen pokud oba stroje akceptují. Pokud M\, M2 byly úplné, je i M úplný. □
IB102 Automaty, gramatiky a složitost, 23.11.2015 17/31
Uzáverové vlastnosti rekursivních a rekursivně spočetných jazyků
Věta. Rekursivně spočetné i rekursivní jazyky jsou uzavřené na zřetězení.
Důkaz.
Nechť L|, Z-2 jsou jazyky akceptované TM M\, M2 s disjunktními množinami stavů. Dvojpáskový stroj M akceptující L1 ./_2 vstupní slovo nedeterministicky rozdělí na dvě části, každou část dá na jednu pásku. Na první části slova spustí M\. Pokud akceptuje, spustí na druhé části AÍ2-M akceptuje jen pokud oba stroje akceptují. Pokud M\, Mz byly úplné, je i M úplný. □
IB102 Automaty, gramatiky a složitost, 23.11.2015
18/31
Uzáverové vlastnosti rekursivních a rekursivně spočetných jazyků
Věta. Rekursivně spočetné i rekursivní jazyky jsou uzavřené na iteraci. Důkaz.
Nechť /.-i je jazyky akceptovaný TM M^. Zkonstruujeme dvojpáskový TM M rozpoznávající Ľv M akceptuje, pokud je na první pásce prázdné slovo. V opačném případě nedeterministicky přesune nějaký neprázdný prefix slova z první pásky na druhou pásku, kde nad ním spustí M\. Pokud M\ zamítne, tak i M zamítne. Jinak opakuje celou proceduru. Je-li M\ úplný, je i M úplný. □
IB102 Automaty, gramatiky a složitost, 23.11.2015
19/31
Uzávěrové vlastnosti rekursivních a rekursivně spočetných jazyků
Věta. Rekursivní jazyky jsou uzavřené na doplněk. Důkaz.
Nechť L| je jazyky akceptovaný úplným (deterministickým) TM M\. Úplný stroj M rozhodující co-L^ získáme záměnou akceptujícího a zamítajícího stavu. □
IB102 Automaty, gramatiky a složitost, 23.11.2015 20/31
Uzávěrové vlastnosti rekursivních a rekursivně spočetných jazyků
Věta. Třída rekursivně spočetných jazyků není uzavřená na doplněk. Důkaz. Provedeme později. □
Třída rekursivně spočetných jazyků je uzavřená na sjednocení, průnik, zřetězení, iteraci, pozitivní iteraci, mocniny.
Třída rekursivních jazyků je uzavřená na sjednocení, průnik, zřetězení, iteraci, pozitivní iteraci, mocniny, doplněk.
IB102 Automaty, gramatiky a složitost, 23.11.2015
21/31
Vztah rekursivních a rekursivně spočetných jazyků
Věta. Jazyk L je rekursivní, právě když jsou jazyky L a co-L rekursivně spočetné.
Důkaz. "=4>" plyne z uzavřenosti rekursivních jazyků na komplement a z toho, že každý rekursivní jazyk je i rekursivně spočetný.
«,_».
Nechť M\, Mz jsou TM rozpoznávající L a co-L. Sestrojíme dvojpáskový stroj M rozhodující L. M nejprve zkopíruje vstupní slovo w na druhou pásku. Pak paralelně vykonává běh M\ na první pásce a běh stroje M2 na druhé pásce. Pokud stroj M\ akceptuje, pak w e La stroj M také akceptuje. Pokud stroj M2 akceptuje, pak w ^ La stroj M zamítá. □
IB102 Automaty, gramatiky a složitost, 23.11.2015
22/31
Problémy jako jazyky
Problém rozhodnout, zda daný řetězec w má vlastnost P lze ztotožnit s množinou {w | w má vlastnost P}.
Objekty O lze kódovat jako slova (O). Problém, zda O má vlastnost P ztotožníme s jazykem {(O) | O má vlastnost P}.
Příklad. Problém rozhodnout, zda daný konečný graf je souvislý, ztotožníme s jazykem {(G) | G je konečný souvislý graf}.
IB102 Automaty, gramatiky a složitost, 23.11.2015
23/31
Kódování TM
Každý TM lze zakódovat do binárního řetězce. Předpokládáme, že M
■ má stavy Q = {q^ cfe, cfe,..., qn}
■ q^ je iniciál ní stav, q2 akceptující stav, q3 zamítající stav
■ má páskovou abecedu l~ = {X1, X2,..., Xz]
■ X1 = > je levá koncová značka, X2 = u je symbol pro prázdné pole
Přechod 6{qh Xj) = (qk, Xh L) kódujeme řetězcem 0''1 Oh 0*10;10. Přechod 6{qhXj) = (qk,XhR) kódujeme řetězcem O'lOňO^IO'lOO.
Z kódů jednotlivých přechodů (v libovolném pořadí) sestavíme kód M:
(M) = 111 kódA 11 kód2 11 ... 11 /cddr 111 Řetězce nekódující žádný TM považujeme za kód TM akceptujícího 0.
Slova kódujeme podobně. Celkem (M, w) = (M)#(w).
IB102 Automaty, gramatiky a složitost, 23.11.2015
24/31
Univerzální Turingův stroj
Věta. Existuje univerzální Turingův stroj U, který dokáže simulovat libovolný zadaný TM na zadaném vstupu:
U akceptuje (M)#{w) <=^> M akceptuje w
Důkaz.
Stroj U je třípáskový. Nejprve ověří, že vstup je tvaru {0,1 }*#{0,1 }* (pokud ne, zamítá). Na první pásce je kód simulovaného stroje M, na druhé pásce probíhá jeho výpočet, na třetí je uložen jeho stav. V každém kroku se na základě simulovaného stavu a obsahu pásky najde na první pásce příslušný přechod, který se pak provede. □
IB102 Automaty, gramatiky a složitost, 23.11.2015
25/31
Rozhodnutelnost problémů
Definice. Problém P odpovídající jazyku L = {(O) | O má vlastnost P} je
■ rozhodnutelný, právě když /.je rekursivní
■ nerozhodnutelný, právě když L není rekursivní
■ částečně rozhodnutelný (semirozhodnutelný), právě když Z_ je rekursivně spočetný
IB102 Automaty, gramatiky a složitost, 23.11.2015
26/31
Problém akceptování
Problém akceptování (problém příslušnosti pro Turingovy stroje) je
problém rozhodnout, zda daný TM M akceptuje dané slovo w nad jeho vstupní abecedou. Problém ztotožníme s jazykem
ACC={(M, w) | M je TM a M akceptuje w}.
Věta. Problém akceptování je částečně rozhodnutelný.
Důkaz. Plyne z existence univerzálního Turingova stroje. □
IB102 Automaty, gramatiky a složitost, 23.11.2015
27/31
Věta. Problém akceptování je nerozhodnutelný.
Důkaz. (Sporem:) Předpokládejme, že existuje TM A rozhodující problém akceptování. Tedy A akceptuje {M,w), právě když M akceptuje w.
S využitím A zkonstruujeme TM V: dostane-li V na vstupu zakódovaný stroj (M), zeptá se stroje A, zda M akceptuje svůj vlastní kód (M) a následně odpověď otočí. Tedy
V akceptuje (M),      pokud   M neakceptuje (M) a
V neakceptuje (M),   pokud   M akceptuje (M).
Nyní spustíme V na vstupu (V)\
V akceptuje (V),     pokud  V neakceptuje (V) a
V neakceptuje (V),   pokud  V akceptuje (V).
To je spor. Stroj A tedy neexistuje a problém akceptování je nerozhodnutelný. □
IB102 Automaty, gramatiky a složitost, 23.11.2015
28/31
Ne-semirozhodnutelné problémy
Věta. Doplněk problému akceptování není ani částečně rozhodnutelný, tedy co-ACC není rekursivně spočetný.
Důkaz.
Důsledek. Třída rekursivně spočetných jazyků není uzavřená na doplněk.
IB102 Automaty, gramatiky a složitost, 23.11.2015 29/31
Problém zastavení
Problém zastavení (halting problém) je problém rozhodnout, zda daný TM M má na daném slově w nad jeho vstupní abecedou konečný výpočet (tedy zda M na vstupu w zastaví). Problém ztotožníme s jazykem
HALT={{M, w) | M je TM a výpočet M na w je konečný}.
Věta. Problém zastavení je částečně rozhodnutelný.
Důkaz. Pomocí univerzálního Turingova stroje simulujeme M na w. Pokud simulovaný výpočet skončí, akceptujeme. □
IB102 Automaty, gramatiky a složitost, 23.11.2015
30/31
Věta. Problém zastavení je nerozhodnutelný.
Důkaz. (Sporem:) Předpokládejme, že existuje úplný TM H rozhodující problém zastavení. Pak ovšem umíme sestrojit TM A rozhodující problém akceptování. Stroj A dekóduje dvojici {M, w) ze vstupu a změní M tak, že místo přechodů do zamítajícího stavu začne cyklit. Modifikovaný stroj M! zastaví, právě když M akceptuje. Nyní stačí spustit H na vstupu (M', w). Dostáváme tedy úplný TM A rozhodující problém akceptování. To je spor. Úplný stroj H tedy neexistuje. □
IB102 Automaty, gramatiky a složitost, 23.11.2015
31/31