náhled|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 , kde: je konečná množina vnitřních stavů je konečná abeceda symbolů na pásce je reprezentace prázdného symbolu je konečná množina vstupních symbolů ( není součástí vstupního řetězce) je počáteční stav přechodová funkce, kde: znamená posun hlavy vlevo znamená posun hlavy vpravo 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 kde , a ; někteří autoři dávají přednost kompaktnímu zápisu , kde je úsek pásky vlevo od hlavy a 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.
Počáteční konfigurace Turingova stroje pro vstup je konfigurace , resp. v kompaktním zápisu .
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). 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í. 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: , , počáteční stav je a . Přechodová funkce by vypadala následovně: vymažeme počáteční nulu a zahájíme přesun hlavy doprava přesouváme hlavu doprava přes nuly, pásku neměníme narazili jsme na první jedničku, měníme stav a pokračujeme v pohybu doprava přesouváme hlavu doprava přes jedničky ocitli jsme se za slovem, vrátíme se před poslední symbol vymažeme poslední jedničku a přesuneme se na předchozí znak pokud jsme v kroku 6 vymazali poslední symbol slova, algoritmus končí přechodem do koncového stavu jinak zahájíme přesun doleva přesouváme hlavu doleva přes jedničky narazili jsme na poslední nulu, měníme stav a pokračujeme v pohybu doleva přesouváme hlavu doleva přes nuly 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. 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í. Nad šipkou představující jeden krok výpočtu je vždy uvedeno číslo použitého pravidla: , . Turingův stroj dospěl do koncového stavu, výpočet končí úspěšně.
Ukázka výpočtu při vstupu 001: , . Ale není definováno, výpočet končí neúspěšně. Do stavu se náš stroj dostane po vymazání poslední 1. U slova 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: . Výpočet opět končí neúspěšně, protože přechodová funkce není definována. V korektním slově řetězec jedniček zahájený za první nulou pokračuje až do konce slova, ve stavu tedy stroj může na pásce najít jen symboly 1 nebo .
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 (hlava zůstane na místě)
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. 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ů (). 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:
nedeterministický TS (NTS) umožňuje „výběr z více možností“ nebo (kde nebo značí potenční množinu množiny .) Idea důkazu: NTS si můžeme představit jako strom. 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. 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ší zpravidla 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