Turingův stroj

Turingův stroj je zařízení, které pracuje se vstupní páskou, vnitřími stavy a předpisy chování. Zkráceně: Přečte znak na pásce a podle toho, v jakém je stavu, pásku na daném místě přepíše (nebo nepřepíše) jiným znakem, a posune (nebo neposune) čtecí hlavu doprava nebo doleva. Takto pracuje do té doby, dokud nedosáhne konce pásky (to znamená neukončí výpočet). V případě, že se stroj zastaví v průběhu výpočtu, znamená to, že vstupní slovo není automatem rozpoznáno (je možné jednoduše vyzkoušet například změnou vstupního slova z prvního příkladu z ##0011 na #10011).

Obecný turingův stroj je něco jako "turingův stroj na druhou". Jeho vstupní páska obsahuje kromě vstupního slova i celý popis chování simulovaného stroje.

Tento obecný turingův stroj ("pod kapotou" je takřka skutečný Turingův stroj implementovný prakticky výhradně pomocí case konstrukcí v javascriptu) umožňuje simulovat turingovy stroje se vstupní abecedou #01. Sám používá abecedu o něco složitější. Tato skutečnost sice znemožňuje spustit stroj na jeho vlastní kód, ovšem výrazně zpřehledňujě zápis.

Syntaxe:

Syntaxi vysvětlím na prvním příkladu (B$011100|00111000|$$|00111000|0001110$$||0001110$##0011).

Kód simulovaného stroje obsahuje:

Znak označující začátek pásky ('B').
Definici samotného stroje (popis jeho chování). Popisy chování pro jednotlivé stavy jsou odděleny znakem '$'. Popis chování stroje se tedy v kódu nachází mezi prvním a posledním '$' včetně.
Znaky '|' Jsou odděleny předpisy chování stroje pro jednotlivé znaky v daných stavech. (Popsáno níže). Není-li mezi znaky '|' a '$' nebo mezi dvěma znaky '|' žádný předpis, znamená to, že daný znak není v daném stavu přijímán (v prvním stavu automat nepřijímá '1' (třetí předpis v pořadí prázdný), ve druhém stavu nepřijímá '#' (první předpis v pořadí prázdný) a ve třetím stavu přijímá pouze '1' (pouze třetí předpis v pořadí existuje).
Vstupní slovo, které má simulovaný stroj zpracovat. Je uvedeno za posledním znakem '$'.

Popis chování pro daný znak a daný stav obsahuje po řadě:

Sadu nul, udávajících do kterého stavu má automat přejít
Sadu jedniček, určujících směr pohybu hlavy stroje
Sadu nul, určujících znak, který má stroj zapsat na pásku.

Například kód 011100 v prvním oddíle (tedy pro znak '#' prvního stavu znamená, že automat přejde (zůstane) v prvním stavu (první nula), posune hlavu doprava (tři jedničky) a zapíše na pásku znak '0' (dvě nuly).

Během výpočtu používá stroj pomocné znaky @ a ^, které slouží k označení míst na pásce, se kterými právě pracuje.