Tu ringů v stroj - syntaxe Definice. (Deterministický) Turingův stroj (Turing Machine, TM) je devítice M = (Q, E, r, >, u, S, q0, qacc, qrej), kde ■ Q je konečná množina, jejíž prvky nazýváme stavy, ■ E je konečná množina, tzv. vstupní abeceda, ■ r je konečná množina, tzv. pracovní abeceda, E c r, ■ o g r \ E je levá koncová značka, ■ u g r \ E je symbol označující prázdné políčko, m S: (Q \ {qacc, qrej}) x ľ Q x V x {L, R} je totální přechodová funkce, ■ q0 e Q je počáteční stav, ■ Qacc e Q je akceptující stav, ■ qrej g Q je zamítající stav. IB102 Automaty, gramatiky a složitost, 10.11.2014 1/31 Dále požadujeme, aby pro každé g g Q existoval p g Q takový, že S(q, >) = (p, o, R) (tj. o nelze přepsat ani posunout hlavu za okraj pásky). Označení. uu = uuuuuu... Definice. Konfigurace Turingova stroje je trojice {q, z, n) g Q x {yuw | y g r*} x N0, kde ■ q je stav, ■ yuw je obsah pásky, ■ n značí pozici hlavy na pásce. Počáteční konfigurace pro vstup w g Z* je trojice (g0, >wuw, 0). Akceptující konfigurace je každá trojice tvaru {qacc, z, n). Zamítající konfigurace je každá trojice tvaru (qrej, z, n). IB102 Automaty, gramatiky a složitost, 10.11.2014 2/31 Výpočet Tu ringová stroje Označení. Pro libovolný nekonečný řetěz z nad l~, zn označuje n-\ý 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 |-^- takto: (q,snb(z),n+1) pro 5(p,zn) = (q, b, R) (g,sg(z),n-1) pro S{p,zn) = {q,b,L) IB102 Automaty, gramatiky a složitost, 10.11.2014 3/31 Výpočet TM M na vstupu w je maximálni (konečná nebo nekonečná) posloupnost konfigurací K0, K-\ ,K2,..., kde K0 je počáteční konfigurace pro w a K; |-^- K/+1 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) = {iver|M akceptuje w}. IB102 Automaty, gramatiky a složitost, 10.11.2014 4/31 Ukázky Tu ringový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, 10.11.2014 5/31 Vícepáskový Turingů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 \ {qacc, Qrej}) X Yk -+ Q X Yk X {L, R}k. Konfigurace mají tvar (q,z-\,... ,zk,n-\,... ,nk) e Qx(r*.{utJ})/cxNQ. Počáteční konfigurace pro w e Z* je (q0, \>wuw, >uw,..., >uw, 0,..., 0). Definice akceptující/zamítající konfigurace a |-^- se změní podobně. IB102 Automaty, gramatiky a složitost, 10.11.2014 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. Q Simulace jednoho kroku = zjistit informace pod hlavami, zapsat nové a posunout hlavy. B Je-li třeba další políčko nějaké pásky posuneme zbývající obsah. IB102 Automaty, gramatiky a složitost, 10.11.2014 □ 7/31 Nedeterministický Turingův stroj Definice. Nedeterministický Turingův stroj M je definován stejně jako TM s výjimkou přechodové funkce 5, která je definována jako totální funkce 5 : (Q \ {qacc, qrej}) x r 2a^^Rl 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) [j^- (q,snb(z),n+ 1) jestliže (q,b, R) g S(p,zn) (p,z,n) Yjj- (q,snb(z),n-A) jestliže (q,b,L) e 5(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, 10.11.2014 8/31 Ekvivalence nedeterministického a deterministického TM Věta. Pro každý nedeterministický Turingův stroj J\f existuje ekvivalentní deterministický TM. Intuice: IB102 Automaty, gramatiky a složitost, 10.11.2014 9/31 Důkaz. Sestrojíme 3-páskový deterministický TM prozkoumávající výpočtový strom stroje M. Tento 3-páskový stroj lze převést na jednopáskový deterministický TM. Nechť k = max{|č(qr,z)| | q e Q \ {qaCc, Qrej},z e 1. 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,..., k}* 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, 10.11.2014 Hledáme akceptující konfiguraci ve výpočtovém stromě prohledáním do šířky. Kontrola jednoho uzlu výpočtového stromu: □ Zkopíruj první pásku na druhou. B Na 2. pásce simuluj M, 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, 10.11.2014 11/31 Další varianty Tu ringová 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, 10.11.2014 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, 10.11.2014 13/31 Turingovy stroje a třídy jazyků Věta. Jazyk L je rekursivně spočetný (tj. generovaný gramatikou typu 0) " plyne z uzavřenosti rekursivních jazyků na komplement a z toho, že každý rekursivní jazyk je i rekursivně spočetný. Nechť M:, M2 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 i na první pásce a běh stroje M2 na druhé pásce. Pokud stroj akceptuje, pak w g L a stroj M také akceptuje. Pokud stroj M2 akceptuje, pak w ^ La stroj M zamítá. □ IB102 Automaty, gramatiky a složitost, 10.11.2014 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, 10.11.2014 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 = {qA, q2, q3, ■ ■ ■, Qn} m q-\ je iniciální stav, q2 akceptující stav, q3 zamítající stav ■ má páskovou abecedu r = {X-\, X2,..., Xz} m X-\ = o je levá koncová značka, X2 = u je symbol pro prázdné pole Přechod 6(qi,Xj) = {qk,XhL) kódujeme řetězcem O'KVIO^IO'lO. Přechod 6(qi,Xj) = {qk,Xh R) kódujeme řetězcem O'KVIO^IO'lOO. Z kódů jednotlivých přechodů (v libovolném pořadí) sestavíme kód M: (M) = 111 kód^ 11 kód2 11 ... 11 kódr 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, 10.11.2014 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)