Turingův stroj: Porovnání verzí
Smazaný obsah Přidaný obsah
→Konfigurace: doplněn kompaktní zápis značka: editace z Vizuálního editoru |
→Příklad Turingova stroje: Přepracován příklad tak, aby používal jednodušší algoritmus a odpovídal definici TS. značka: editace z Vizuálního editoru |
||
Řádek 38:
== Příklad Turingova stroje ==
Napíšeme jednoduchý TS, který bude mít za úkol zjistit, zda slovo napsané na pásku má tvar 0<sup>n</sup>1<sup>n</sup>, 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: <math>Q = \{q_0, q_1, q_2, q_3, q_4, q_5, q_6, q_7\}</math>, <math>\Gamma = \{0, 1, b \}</math>, počáteční stav je <math>q_0</math> a <math>F = \{ q_7 \}</math>. Přechodová funkce by vypadala následovně:
# <math>\delta( q_0, 0 ) = ( q_1, b, R)</math> vymažeme počáteční nulu a zahájíme přesun čtecí hlavy doprava
# <math>\delta( q_1, 0 ) = ( q_1, 0, R)</math> přesouváme hlavu doprava přes nuly, pásku neměníme
# <math>\delta( q_1, 1 ) = ( q_2, 1, R)</math> narazili jsme na první jedničku, měníme stav a pokračujeme v pohybu doprava
# <math>\delta( q_2, 1 ) = ( q_2, 1, R)</math> přesouváme hlavu doprava přes jedničky
# <math>\delta( q_2, b ) = ( q_3, b, L)</math> ocitli jsme se za slovem, vrátíme se před poslední symbol
# <math>\delta( q_3, 1 ) = ( q_4, b, L)</math> vymažeme poslední jedničku a přesuneme se na předchozí znak
# <math>\delta( q_4, b ) = ( q_7, b, R)</math> pokud jsme v kroku 6 vymazali poslední symbol slova, algoritmus končí přechodem do koncového stavu
# <math>\delta( q_4, 1 ) = ( q_5, 1, L)</math> jinak zahájíme přesun doleva
# <math>\delta( q_5, 1 ) = ( q_5, 1, L)</math> přesouváme hlavu doleva přes jedničky
# <math>\delta( q_5, 0 ) = ( q_6, 0, L)</math> narazili jsme na poslední nulu, měníme stav a pokračujeme v pohybu doleva
# <math>\delta( q_6, 0 ) = ( q_6, 0, L)</math> přesouváme hlavu doleva přes nuly
# <math>\delta( q_6, b ) = ( q_0, b, R)</math> 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:
* Čtecí 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 čtecí hlava může takto poznat konec slova. Začátek slova může poznat stejným způsobem
Ukázka výpočtu výše uvedeného Turingova stroje při vstupu <code>0011</code>. 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: <math>q_0 0011</math> <math>\overset{1}{ \rarr}</math> <math>q_1 011</math> <math>\overset{2}\rarr</math> <math>0 q_1 11</math> <math>\overset{3}\rarr</math> <math>01 q_2 1</math>,<math>\overset{4}\rarr</math> <math>011 q_2</math> <math>\overset{5}\rarr</math> <math>01 q_3 1</math> <math>\overset{6}\rarr</math> <math>0 q_4 1</math> <math>\overset{8}\rarr</math> <math>q_5 01</math> <math>\overset{10}\rarr</math> <math>q_6 b01</math> <math>\overset{12}\rarr</math> <math>q_0 01</math> <math>\overset{1}\rarr</math> <math>q_1 1</math> <math>\overset{3}\rarr</math> <math>1 q_2</math> <math>\overset{5}\rarr</math> <math>q_3 1</math> <math>\overset{6}\rarr</math> <math>q_4 b</math> <math>\overset{7}\rarr</math> <math>q_7 b</math>. Turingův stroj dospěl do koncového stavu, výpočet končí úspěšně.
Ukázka výpočtu při vstupu <code>001</code>: <math>q_0 001</math> <math>\overset{1}\rarr</math> <math>q_1 01</math> <math>\overset{2}\rarr</math> <math>0 q_1 1</math> <math>\overset{3}\rarr</math> <math>01 q_2</math>,<math>\overset{5}\rarr</math> <math>0 q_3 1</math> <math>\overset{6}\rarr</math> <math>q_4 0</math>. Ale <math>\delta(q_4, 0)</math> není definováno, výpočet končí neúspěšně. Do stavu <math>q_4</math> se náš stroj dostane po vymazání poslední 1. U slova <math>0^n1^n</math> 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: <math>q_0 0101</math> <math>\overset{1}\rarr</math> <math>q_1 101</math> <math>\overset{3}\rarr</math> <math>1 q_2 01</math>. Výpočet opět končí neúspěšně, protože přechodová funkce <math>\delta(q_2, 0)</math> není definována. V korektním slově řetězec jedniček zahájený za první nulou pokračuje až do konce slova, ve stavu <math>q_2</math> tedy stroj může na pásce najít jen symboly 1 nebo <math>b</math>.
== Modifikace ==
| |||