Turingův stroj - syntaxe
Definice. (Deterministický) Turingův stroj (Turing Machine, TM) je
devítice M = (Q, Z, r, >, u, S, q0, 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 ľ -> Q x V x {L, R}
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, 14.11.2016 1/24
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, >wuUJ, 0). Akceptující konfigurace je každá trojice tvaru (qacc, n)-Zamítající konfigurace je každá trojice tvaru (grey, z, n).
IB102 Automaty, gramatiky a složitost, 14.11.2016
2/24
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 5{p, zn) = (q, b, R) ^ (q, sg(z), n - 1)    pro č(p, zn) = (q, b, L)
IB102 Automaty, gramatiky a složitost, 14.11.2016
3/24
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 Kj      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(A^) = {w g Z* | .M akceptuje w}.
IB102 Automaty, gramatiky a složitost, 14.11.2016
4/24
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, 14.11.2016
5/24
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 (q,z1,... ,zk, n-i ,...,nk) e Qx(r*.{u^})/cxN^. Počáteční konfigurace pro w e 51* je (g0, >^uw, >u^..., >u^ 0,..., 0)
Definice akceptující/zamítající konfigurace a her se změní podobně.
M
IB102 Automaty, gramatiky a složitost, 14.11.2016 6/24
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, 14.11.2016
□
7/24
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 x {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),a7+1) jestliže R) e S{p,zn)
(p,z,n) ^ (g,sg(z),/7-1) jestliže (g, £>, /_) g 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, 14.11.2016
8/24
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, 14.11.2016
9/24
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,qrej},z e V}.
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, 14.11.2016 10/24
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, 14.11.2016
11/24
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, 14.11.2016
12/24
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, 14.11.2016
13/24
Turingovy stroje a třídy jazyků
Věta. Jazyk L je rekursivně spočetný (tj. generovaný gramatikou typu 0) <=^> L 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, 14.11.2016
14/24
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, 14.11.2016
15/24
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-i, L2 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     , M2 byly úplné, je i M úplný. □
IB102 Automaty, gramatiky a složitost, 14.11.2016 16/24
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ť L|, /_2 jsou jazyky akceptované TM M\, Mz 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, 14.11.2016 17/24
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-i, L2 jsou jazyky akceptované TM M\, M2 s disjunktními množinami stavů. Dvojpáskový stroj M akceptující L1 .L2 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     , M2 byly úplné, je i M úplný. □
IB102 Automaty, gramatiky a složitost, 14.11.2016
18/24
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, 14.11.2016
19/24
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-i 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, 14.11.2016 20/24
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, 14.11.2016
21/24
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\, 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      na první pásce a běh stroje M2 na druhé pásce. Pokud stroj     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, 14.11.2016
22/24
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, cfe, qr3,..., qn}
■ q^ je iniciál ní stav, q2 akceptující stav, q3 zamítající stav
■ má páskovou abecedu l~ = {X1, X2,..., Xz}
■ = > je levá koncová značka, X2 = u je symbol pro prázdné pol
Přechod 5{qh Xfj = (qk, Xh Ľ) kódujeme řetězcem 0'1 (V 10*10'10. Přechod 5{qh Xj) = \qk, Xh R) kódujeme řetězcem 0'1 (V 10*10'100.
Z kódů jednotlivých přechodů (v libovolném pořadí) sestavíme kód M:
(M) = 111 /cdcy1 11 /cdcř2 11 ... 11 /cdc/r 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, 14.11.2016
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, 14.11.2016
24/24