Turingův stroj

Umělecké znázornění Turingova stroje Turingův stroj (TS) je teoretický model počítače popsaný matematikem Alanem Turingem, který se používá pro modelování algoritmů v teorii vyčíslitelnosti.

Skládá se z řídicí jednotky s konečným počtem stavů, konečné množiny pravidel, která definují přechodovou funkci, a pravostranně nekonečné pásky pro vstup a zápis mezivýsledků.

Jeden ze způsobů vyjádření Churchovy-Turingovy teze říká, že ke každému algoritmu existuje ekvivalentní Turingův stroj.

Od výpočetní síly Turingova stroje se odvozuje turingovská úplnost: turingovsky úplné jsou právě ty programovací jazyky nebo počítače, které mají stejnou výpočetní sílu jako Turingův stroj.

Definice

Turingův stroj je uspořádaná sedmice \ M=(Q, \Gamma, b, \Sigma, q_0, \delta, F), kde: * Q je konečná množina vnitřních stavů * \Gamma je konečná abeceda symbolů na pásce * b\in \Gamma je reprezentace prázdného symbolu * \Sigma \subseteq \Gamma \setminus \{b\} je konečná množina vstupních symbolů (b není součástí vstupního řetězce) * q_0\in Q je počáteční stav * \delta: (Q \setminus F)\times\Gamma\rightarrow Q\times\Gamma \times \{L,R\} přechodová funkce, kde: ** L znamená posun hlavy vlevo ** R znamená posun hlavy vpravo * F\subseteq Q je množina koncových stavů

Konfigurace

Konfigurace Turingova stroje je tvořena aktuálním stavem q, počátečním úsekem pásky s obsahujícím neprázdné symboly, a informací o pozici hlavy (tvořenou např. číslem buňky n).

Formálně může být konfigurace definována jako uspořádaná trojice (q, s, n), kde q \in Q, s \in \Gamma^* a n \in \mathbb{N}_0; někteří autoři dávají přednost kompaktnímu zápisu s_1qs_2, kde s_1 \in \Gamma^* je úsek pásky vlevo od hlavy a s_2 \in \Gamma^* je úsek pásky začínající políčkem, na kterém stojí hlava; v tomto případě musí být množiny stavů a symbolů na pásce disjunktní, tj. Q \cap \Gamma = \emptyset.

Počáteční konfigurace Turingova stroje pro vstup w\in\Gamma^* je konfigurace (q_0,w,0), resp. v kompaktním zápisu q_0w.

Výpočet

Na začátku výpočtu je Turingův stroj v počáteční konfiguraci a na pásce je zapsané vstupní slovo. Dále pracuje v jednotlivých krocích: # pokud je aktuální stav koncovým stavem, výpočet končí úspěchem # hlava přečte vstupní symbol z buňky, na které se právě nachází # není-li pro aktuální stav a přečtený symbol definovaná hodnota přechodové funkce, výpočet končí neúspěchem # jinak se provede „instrukce“ popsaná hodnotou přechodové funkce (u nedeterministických strojů se v případě více možných přechodů vybere jeden náhodně), což znamená: #* změní se stav #* na aktuální pozici hlavy se zapíše příslušný symbol #* hlava se posune o jednu pozici doleva nebo doprava

Neformální popis

TS můžeme chápat jako primitivní počítač, jehož program je dán přechodovou funkcí, vstupní data jsou tvořena vstupním slovem, páska slouží jako paměť a výstupem je pouze informace, zda výpočet skončil úspěchem, neúspěchem nebo pokračuje; alternativně můžeme za výsledek považovat i obsah pásky v okamžiku ukončení výpočtu. Existují různé modely TS, za dodržení určitých zásad (především možnost použití nekonečně velké pásky) jsou však co do možností výpočtů ekvivalentní (i když se mohou výrazně lišit efektivitou). +more Samotný TS pracuje podobně jako konečný automat, ale s tím zásadním rozdílem, že má nekonečně velkou pásku, na kterou může zapisovat a libovolně se po ní může pohybovat. Na začátku definujeme stavy a přechodové funkce, přijímající a zamítající stav a abecedu, nad kterou TS pracuje. Poté na pásku TS vložíme slovo, které se skládá ze symbolů abecedy, a TS se pokusí toto slovo přijmout. Při tom můžeme po TS požadovat, aby nějakým způsobem pozměnil symboly na pásce, čímž můžeme realizovat nějaký výpočet, například násobení. TS může výpočet ukončit dvěma způsoby: buď dojde do koncového stavu (což interpretujeme, že TS vstupní slovo w přijal, akceptoval), nebo se dostane do situace, kdy pro danou kombinaci stavu a vstupního symbolu není definována žádná činnost (což interpretujeme jako odmítnutí vstupního slova w). Třetí možností je, že výpočet TS nikdy neskončí.

Příklad Turingova stroje

Popíšeme jednoduchý TS, který bude mít za úkol zjistit, zda slovo napsané na pásku má tvar 0n1n, n>0 (zda řetězec obsahuje n nul a následně n jedniček). Víme, že konečný automat tento problém řešit neumí, ale zásobníkový automat to již řešit umí. +more Ukážeme, jak by vypadal TS M, který by tento problém vyřešil.

Základní myšlenkou algoritmu je, že náš Turingův stroj vždy vymaže počáteční 0, přesune hlavu na konec slova, vymaže z něj poslední 1 a přesune se zpět na začátek slova. Tuto činnost opakuje, dokud slovo nevymaže nebo se nedostane do stavu, kdy další krok není definován (v tom případě slovo do jazyka nepatří).

Formální zápis: Q = \{q_0, q_1, q_2, q_3, q_4, q_5, q_6, q_7\}, \Gamma = \{0, 1, b \}, počáteční stav je q_0 a F = \{ q_7 \}. Přechodová funkce by vypadala následovně: # \delta( q_0, 0 ) = ( q_1, b, R) vymažeme počáteční nulu a zahájíme přesun hlavy doprava # \delta( q_1, 0 ) = ( q_1, 0, R) přesouváme hlavu doprava přes nuly, pásku neměníme # \delta( q_1, 1 ) = ( q_2, 1, R) narazili jsme na první jedničku, měníme stav a pokračujeme v pohybu doprava # \delta( q_2, 1 ) = ( q_2, 1, R) přesouváme hlavu doprava přes jedničky # \delta( q_2, b ) = ( q_3, b, L) ocitli jsme se za slovem, vrátíme se před poslední symbol # \delta( q_3, 1 ) = ( q_4, b, L) vymažeme poslední jedničku a přesuneme se na předchozí znak # \delta( q_4, b ) = ( q_7, b, R) pokud jsme v kroku 6 vymazali poslední symbol slova, algoritmus končí přechodem do koncového stavu # \delta( q_4, 1 ) = ( q_5, 1, L) jinak zahájíme přesun doleva # \delta( q_5, 1 ) = ( q_5, 1, L) přesouváme hlavu doleva přes jedničky # \delta( q_5, 0 ) = ( q_6, 0, L) narazili jsme na poslední nulu, měníme stav a pokračujeme v pohybu doleva # \delta( q_6, 0 ) = ( q_6, 0, L) přesouváme hlavu doleva přes nuly # \delta( q_6, b ) = ( q_0, b, R) dostali jsme se před slovo, vrátíme se na jeho první znak a začínáme zase od začátku, slovo je nyní o dva znaky kratší Několik poznámek k algoritmu: * hlava se může libovolně pohybovat po pásce tím způsobem, že přečte symbol A, zapíše (stejný) symbol A a posune se doleva nebo doprava. +more Tím se hlava může posunout o libovolný počet míst, aniž by cokoliv na pásce změnila. Tento přístup je použit ve většině kroků (s výjimkou kroků 1 a 6, kde se obsah pásky mění). * Místo vymazání by bylo možné zpracované symboly 0 a 1 „škrtnout“, tedy nahradit speciálním znakem, který by se pro tento účel přidal do páskové abecedy. * Za posledním symbolem ze vstupního slova w se nachází prázdné symboly, takže hlava může takto poznat konec slova. Začátek slova může poznat stejným způsobem. V opačném případě by bylo nutné například přidat speciální symbol před začátek slova w, který označí začátek slova.

Ukázka výpočtu výše uvedeného Turingova stroje při vstupu 0011. Zapíšeme ji jako posloupnost po sobě následujících konfigurací. +more Nad šipkou představující jeden krok výpočtu je vždy uvedeno číslo použitého pravidla: q_0 0011 \overset{1}{ \rarr} q_1 011 \overset{2}\rarr 0 q_1 11 \overset{3}\rarr 01 q_2 1,\overset{4}\rarr 011 q_2 \overset{5}\rarr 01 q_3 1 \overset{6}\rarr 0 q_4 1 \overset{8}\rarr q_5 01 \overset{10}\rarr q_6 b01 \overset{12}\rarr q_0 01 \overset{1}\rarr q_1 1 \overset{3}\rarr 1 q_2 \overset{5}\rarr q_3 1 \overset{6}\rarr q_4 b \overset{7}\rarr q_7 b. Turingův stroj dospěl do koncového stavu, výpočet končí úspěšně.

Ukázka výpočtu při vstupu 001: q_0 001 \overset{1}\rarr q_1 01 \overset{2}\rarr 0 q_1 1 \overset{3}\rarr 01 q_2,\overset{5}\rarr 0 q_3 1 \overset{6}\rarr q_4 0. Ale \delta(q_4, 0) není definováno, výpočet končí neúspěšně. +more Do stavu q_4 se náš stroj dostane po vymazání poslední 1. U slova 0^n1^n mohou v této situaci nastat jen dva případy - buď se tím slovo vyprázdnilo (instrukce 7) nebo ještě jeho část zbývá, ta ale musí končit jedničkami (instrukce 8).

Ukázka výpočtu při vstupu 0101: q_0 0101 \overset{1}\rarr q_1 101 \overset{3}\rarr 1 q_2 01. Výpočet opět končí neúspěšně, protože přechodová funkce \delta(q_2, 0) není definována. +more V korektním slově řetězec jedniček zahájený za první nulou pokračuje až do konce slova, ve stavu q_2 tedy stroj může na pásce najít jen symboly 1 nebo b.

Modifikace

Existují různé modifikace Turingova stroje, které mají stejnou sílu, tzn. že přijímají stejnou třídu jazyků jako základní model.

* TS s možností provedení výpočtu bez posunu hlavy ** přechodová funkce je rozšířena o N (hlava zůstane na místě) ** \delta: Q\times\Gamma\rightarrow Q\times\Gamma \times \{L,R,N\} ** Idea důkazu, že se jedná o výpočetně stejně silný TS: posun N (žádný posun hlavy) můžeme na běžném TS zařídit tak, že hlava přečte vstupní symbol z buňky, na které se nachází, provede příslušnou operaci a posune se doprava (R). Nyní opět přečte symbol z buňky, zapíše tam stejný symbol (tj. +more nezmění symbol, na kterém se hlava nachází) a posune se doleva (L). Tím jsme dostali hlavu do předchozího umístění a žádný jiný symbol nebyl změněn. Pokud máme jako výchozí TS s levou zarážkou (páska je nekonečná jen zprava), je důležité posouvat se nejprve vpravo, protože pokud bychom se posunuli doleva a hlava by stála na prvním symbolu, posunula by se hlava v druhém kroku na druhý symbol.

* TS s oboustranně nekonečnou páskou ** páska není zleva ohraničená ** možný posun hlavy doleva z libovolné konfigurace ** Idea důkazu: *** Jako první dokážeme, že na běžném TS (označme TS) dokážeme nasimulovat TS s oboustranně nekonečnou páskou (označme TS∞). V TS si zvolíme takový symbol D, který se nenachází v abecedě symbolů (\Gamma). +more Na začátku se tento symbol nachází nalevo od vstupního slova w. Nyní nadefinujeme TS tak, že ve chvíli, kdy hlava dosáhne na symbol D, posune celý obsah pásky napravo od symbolu D o jednu buňku doprava a vrátí hlavu na vzniklou prázdnou buňku, které vznikla mezi obsahem pásky a symbolem D. Tím dosáhneme funkčnosti TS∞. *** A nyní naopak. Zlomíme TS∞ tak, aby nám vznikly dva TS s zleva omezenou páskou. Tyto dvě pásky dáme pod sebe a nadefinujeme přechody tak, aby když hlava dojde na levý konec horní pásky, aby při dalším pokusu o posun doleva přešla na spodní pásku a pokračovala doprava. A naopak. Když se hlava dostane na levý okraj spodní pásky a bude chtít jít doprava (na spodní stopě musí být směry prohozené), hlava se přesune na horní pásku a pokračuje dále. Okraj pásky poznáme podle pomocného symbolu D, podobně jako v předchozím případě.

* n-páskový TS ** čte z a zapisuje do více pásek najednou ** jediná změna je v přechodové funkci: :\delta: Q\times\Gamma^n\rightarrow Q\times(\Gamma\times\{L,R,N\})^n

* nedeterministický TS (NTS) ** umožňuje „výběr z více možností“ ** \delta: Q\times\Gamma\rightarrow \mathcal{P}(Q\times\Gamma\times\{L,R,N\}) nebo \delta: Q\times\Gamma\rightarrow 2^{Q\times\Gamma\times\{L,R,N\}} (kde \mathcal{P}(X) nebo 2^X značí potenční množinu množiny X. ) ** Idea důkazu: NTS si můžeme představit jako strom. +more Kořenem stromu je počáteční konfigurace NTS a každá větev z tohoto uzlu představuje jednu možnost, kudy může NTS jít. Pokud může například NTS přečíst jedničku a zapsat nulu a nebo přečíst nulu a zapsat jedničku, povedou z uzlu dvě větve, které reprezentují tyto možnosti. My předpokládáme, že NTS vybere vždy tu správnou cestu. Deterministicky bychom mohli tento stroj naprogramovat tak, že projdeme všechny větve NTS, ze kterých může NTS vybírat a když nalezneme alespoň jednu akceptující větev, respektive alespoň jeden akceptující uzel (list), stroj uspěl a dané slovo přijímá. Pokud bude ve všech větvích (listech) zamítající stav, stroj slovo zamítá. Pokud je alespoň jedna větev nekonečná a ostatní zamítající, stroj cyklí. Důležité je, jak budeme strom procházet. Pokud projdeme strom do hloubky, hrozí nám zacyklení. Například pokud bude hned první cesta nekonečná, ale všechny ostatní cesty by vedly do přijímajícího stavu, stroj by fungoval špatně, protože by se utopil hned v první cestě. Pokud ale projdeme do šířky, toto se nám nestane, protože budeme po částech procházet všechny možné větve najednou a postupně narazíme na všechny zamítající a přijímající stavy (ten nám ale stačí jeden). Ani tento postup nám ale nezaručí, že se vyhneme cyklům, pokud není nalezen žádný přijímající stav. Zbývá-li již poslední větev, která je nekonečná a ostatní cesty vedly do zamítajícího stavu, NTS se zacyklí stejně jako se zacyklí TS. Proto není NTS silnější nástroj než TS, oba přijímají stejnou množinu jazyků.

Subrutiny

Tvorba složitějších TS není jednoduchá záležitost a subrutiny slouží k usnadnění této činnosti. Subrutina je množina stavů, která obsahuje počáteční a koncový stav. +more Zpravidla řeší nějaký dílčí problém v TS. V běžném programování má ekvivalent ve funkci, která také má nějaké vstupní a výstupní stavy a řeší z pravidla nějaký dílčí problém celého programu. V předchozím příkladě kontroly 0n1n by mohla být subrutina například vrácení hlavy na začátek nebo kontrola, zda už máme označena všechna čísla.

Zakódování Turingova stroje

Každý Turingův stroj můžeme zakódovat do jednoho řetězce. Existuje nekonečně mnoho způsobů, jak TS zakódovat, záleží na vlastní definici. +more Můžeme například očíslovat všechny stavy, očíslovat všechny symboly z abecedy a očíslovat všechny směry, kterými se může hlava vydat. Následně můžeme přechodovou funkci (q1,a2)→(q3,t6,L1), kde dolní indexy označují očíslování, zakódovat takto: 01001000100000010. Jako oddělovač jsme použili jedničku a počet nul se vždy rovná očíslování daného objektu. Více různých přechodových funkcí můžeme oddělit dvěma jedničkami, takže pokud bychom přidali ještě funkci (q1,b3)→(q3,t6,R2), získali bychom řetězec 01001000100000010110100010001000000100. Takto můžeme zakódovat všechny přechodové funkce. Zbývá už jen označit startovací, přijímající a ukončovací stav, což můžeme udělat například tak, že startovací stav bude mít vždy index jedna, přijímající dva a zamítající tři. Do tohoto formátu pak můžeme zakódovat libovolný TS. Důsledkem tohoto faktu je, že množina všech Turingových strojů je spočetná.

Univerzální TS

Univerzální Turingův stroj je takový TS U, který jako vstup přijímá kód jiného TS T (jeho Gödelovo číslo) a vstupní slovo stroje T. Dokáže rozkódovat přechodovou funkci stroje T a výpočet tohoto stroje simulovat. +more Univerzální TS dokáže vypočítat libovolnou částečně rekurzivní funkci (neboli je ekvivalentní k univerzální částečně rekurzivní funkci), rozhoduje jakýkoliv rekurzivní jazyk a přijímá libovolný rekurzivně spočetný jazyk.

Univerzální jazyk Lu

Univerzální jazyk Lu je takový jazyk, který obsahuje dvojice TS a řetězec, přičemž tento TS daný řetězec přijímá. Platí: Lu = {[M, w]| TS M přijímá slovo w}. +more Tento jazyk je rekurzivně spočetný. Abychom zjistili, zda daná dvojice patří do tohoto jazyka, potřebovali bychom sestrojit TS Tu, který by rozhodoval problém, zda TS M přijímá slovo w. K tomu budeme potřebovat Univerzální TS. Tento TS Tu bude postupovat tak, že na vstupu vezme libovolný (zakódovaný) TS M a slovo w a nasimuluje činnost TS M při vstupu w. Neexistuje jiná možnost jak zjistit, jestli TS M přijímá slovo w než ta, že prostě do TS M to slovo w dáme a počkáme, jak nám TS M odpoví. Takže Universální TS Tu nasimuluje činnost TS M a pokud TS M slovo přijme, i Tu dvojici přijme. Pokud TS M slovo odmítne, i Tu dvojici odmítne. Problém nastane, když se TS M při vstupu w zacyklí. Neexistuje postup, jakým by měl TS Tu poznat, že se vnitřní TS M zacyklil, takže se zacyklí taktéž. Náš Tu je tudíž schopen rozpoznat a přijmout všechny dvojice, které do jazyka Lu patří, ale není schopen identifikovat všechny dvojice, které do jazyka Lu nepatří. A to v případě, kdy se TS M při vstupu w zacyklí. Přičemž takový TS jistě existuje, například TS, který se zacyklí pro jakýkoliv vstup.

Redukce problémů

Některé problémy (Turingovy stroje) můžeme redukovat na jiné, což nám může pomoci při hledání důkazu, zda daný jazyk je rekurzivní jazyk, rekurzivně spočetný jazyk nebo zda není ani rekurzivně spočetný jazyk. Modelová situace: Víme, že jazyk A je rekurzivně spočetný (existuje důkaz). +more Chceme zjistit, zda je jazyk B rekurzivní, přičemž platí, že pokud by pro B existoval rozhodovací algoritmus, byli bychom s jeho pomocí schopni rozhodnout také problém A, tedy z A by se rázem stal rekurzivní jazyk. My ale víme, že A není rekurzivní jazyk, proto ani B nemůže být rekurzivní jazyk. Konkrétní příklad:.

Jazyk HALT

Jazyk HALT představuje množinu všech dvojic TS a slovo, pro které platí, že TS pro dané slovo zastaví (buď přijme, nebo odmítne, ale nezacyklí se). Tento jazyk není rekurzivní, protože pokud by tento jazyk byl rekurzivní, byli bychom schopni sestavit algoritmus, který by rozhodoval Univerzální jazyk Lu. +more TS, který by rozhodoval Lu by mohl vypadat následovně (předpokládáme vstup TS M a w, TSHALT je TS, který rozhoduje jazyk HALT):.

# Pomocí TSHALT zjisti, zda M zastaví pro w. # Pokud nezastaví, odmítni slovo. # V opačném případě simuluj TS M pro vstup w a vrať to, co vrátí TS M.

Tento TS by byl schopný identifikovat, zda TS M přijímá slovo w. Nejdříve zjistí, zda daný TS M pro slovo w zastaví. +more Pokud se zacyklí, slovo rovnou odmítne. V opačném případě simuluje činnost M, který už musí vrátit nějaký výsledek, nemůže se zacyklit, to by bylo v rozporu s rozhodnutím TSHALT. Tento TS by tudíž rozhodoval Lu. My ale víme, že to není možné. A pokud není možné rozhodnout Lu, ale pomocí TSHALT by to šlo, znamená to, že HALT nemůže být rekurzivní jazyk.

Jazyk EMPTY

Jazyk EMPTY je množina všech TS, které přijímají prázdný jazyk. Tento jazyk není rekurzivní, protože s jeho pomocí lze řešit Lu. +more Představme si TSEMPTY, který by rozhodoval, zda TS přijímá prázdný jazyk. Nyní sestrojíme TS, který je schopen rozhodnout Lu při vstupu TS M a slova w:.

# Sestrojíme nový TS M1, který odmítne všechna slova krom w; pokud je na vstupu slovo w, simuluje činnost původního TS M. # Pomocí TSEMPTY zjistíme, zda TS M1 přijímá prázdný jazyk. +more # Pokud TS M1 přijímá prázdný jazyk, nepřijímá slovo w. Pokud TS M1 přijímá neprázdný jazyk, přijímá slovo w. Všechna slova krom w totiž musí TS M1 odmítnout, přijímá-li TS M1 neprázdný jazyk, jediné slovo, které může přijímat, je právě w. Přijímá-li TS M1 slovo w, přijímá ho i TS M, protože pro slovo w se chová TS M1 a TS M stejně.

Protože ale víme, že jazyk Lu není rozhodnutelný, nemůže ani jazyk EMPTY být rozhodnutelný/rekurzivní.

Problémy, které TS nedokáže vyřešit

Přestože je TS mocný nástroj, nedokáže vyřešit všechny problémy. Každý Turingův stroj můžeme zakódovat do řetězce skládajícího se z jedniček a nul podobně jako se kódují programy na reálných počítačích. +more Tím máme dokázáno, že Turingových strojů je spočetně mnoho, protože uzávěr nad abecedou {0, 1}* můžeme uspořádat do nekonečné posloupnosti 0, 1, 01, 10, 100, 101, 110, 111, 1000, . a každý Turingův stroj zakódovaný do jedniček a nul tudíž v této posloupnosti nalezneme. Teď dokážeme, že jazyků (= problémů) je nespočetně mnoho. Použijeme k tomu diagonální metodu. Jazyk je vybraná podmnožina z uzávěru nad abecedou. Předpokládejme abecedu A={0,1} a jazyky (- značí, že daný jazyk slovo v prvním řádku neobsahuje, + značí, že obsahuje):.

A* = 0, 1, 01, 10, 100, 101, ... L1 = - - + + - + ... L2 = + - - - - + ... L3 = + + + + + - ... ...

Takže platí, že L1 = {0, 1, 01, 10, 100, 101, . }, tedy L1 = {01, 10, 101, . +more} atd. Nyní sestrojíme jazyk, který jistě nenajdeme v předchozím (nekonečném) výčtu jazyků. Nový jazyk Ln sestrojíme tak, že pokud jazyk Li obsahuje slovo z A* na i-té pozici, jazyk Ln ho obsahovat nebude a naopak. Tak jistě docílíme toho, že nový jazyk Ln se bude lišit alespoň v tomto jednom slově. Takže L1 neobsahuje slovo na prvním místě, tedy slovo 0, takže Ln ho obsahovat bude. Jazyk L2 neobsahuje slovo na druhém místě, 1, takže Ln ho bude obsahovat. Jazyk L3 obsahuje 01, takže Ln ho nebude obsahovat. A tak dále. Ln={0, 1, 01,. }. Jazyk Ln nenajdeme v předchozím výčtu jazyků, protože s každým uvedeným jazykem Li se bude lišit alespoň v tom, zda (ne)obsahuje slovo z A* na i-té pozici. Tím jsme dokázali, že množina všech jazyků (problémů) je nespočetná.

Pokud existuje nespočetně mnoho jazyků (problémů) a spočetně mnoho Turingových strojů, musí nutně existovat problémy, které Turingovy stroje nejsou schopné řešit. Jazyků (problémů) je zkrátka více než Turingových strojů.

Externí odkazy

[url=http://www.earchiv.cz/a94/a432c120.php3]Více informací a popis Turingova stroje[/url]

Kategorie:Výpočetní modely Kategorie:Vyčíslitelnost