Turingovy stroje v prikladech (Prolog)

---

Definice (Turinguv stroj):

Turinguv stroj je petice (Q,A,d,q,F), kde:

- Q je konecna mnozina stavu (vnitrni abeceda)

- A je (vnejsi) abeceda (konecna mnozina pismen)

- q je pocatecni stav (prvek mnoziny Q)

- F je mnozina koncovych stavu (podmnozina mnoziny Q)

- d je prechodova posloupnost (Q-F) x (A+{free}) -> Q x (A+{free}) x {L,N,R}

(free je specialni znak urcujici prazdne policko na pasce).

 

Práce Turingova stroje

Na pasce je v jednotlivych polickach napsane nejake slovo (ostatni policka jsou prazdna, tj. obsahuji znak free). K jednomu policku pasky je prilozena cteci/zapisovaci hlava.

Podle cteneho pismene a vnitrniho stavu se ridici jednotka "rozhodne" o tom, jake pismeno na pasku napise, do jakeho dalsiho vnitrniho stavu prejde a zda se cteci hlava posune o jedno policko vlevo, vpravo nebo zustane na miste (to je dano "instrukcemi" prechodove posloupnosti).

Prace Turingova stroje konci ve chvili, kdy nelze pouzit zadnou dalsi instrukci (tj., kdyz je ridici jednotka v koncovem stavu).

Paska je reprezentovana dvojici seznamu Left-Right, pricemz hlava cte prvni pismeno seznamu Left. Napriklad paska |a|b|c|d|, kde hlava je na pismenu c vypada takto [c,b,a]-[d] (leva cast pasky je tedy zadana v obracenem poradi a nikdy nesmi byt prazdna).

Program se spousti prikazem ?-turing(q0,PocatecniKonfigurace,KoncovaKonfigurace) , kde q0 je pocatecni stav a PocatecniKonfigurace je zadani pasky na vstupu. Vysledkem behu programu je koncovy stav pasky KoncovaKonfigurace.

Chcete-li se o programovacim jazyku Prolog dozvedet vice, podivejte se na stranky Interactive Prolog Guide.

turing(State,[Letter|Left]-Right,FinalTape):-

c(State,Letter,NewState,Write,Move),

move(Move,[Write|Left]-Right,NewTape),

turing(NewState,NewTape,FinalTape).

turing(State,Tape,Tape):-

f(State).

 

move(none,Tape,Tape).

move(left,[X|Left]-Right,NewLeft-NewRight):-

(Left=[] -> NewLeft=[free] ; NewLeft=Left),

(Right=[free] -> NewRight=[X] ; NewRight=[X|Right]).

move(right,Left-[X|Right],NewLeft-Right):-

Left=[free] -> NewLeft=[X] ; NewLeft=[X|Left].

move(right,Left-[],NewLeft-[]):-

Left=[free] -> NewLeft=Left ; NewLeft=[free|Left].

Jedná se samozrejme jen o kostru emulatoru, kterou lze dale rozsirovat. Lze napriklad vypisovat stav pasky po kazdem kroku nebo pridat ladici prostredi umoznujici krokovat provadeni "programu" pro Turinguv stroj.

Nezapomente se podivat na stranku, kde jsou uvedeny priklady programu pro tento emulator.