W maszynie Turinga, w danym stanie, głowica zapisująca wskazuje na określone miejsce na taśmie. Pozostaną symbole z głowy i symbole z prawej strony głowy.
Patrząc na pierwszego, głównego orzecznika:
turing(Tape0, Tape) :-
perform(q0, [], Ls, Tape0, Rs),
reverse(Ls, Ls1),
append(Ls1, Rs, Tape).
To będzie "uruchomić maszynę" wywołując perform/5. Argumenty za perform(Q0, Ls0, Ls, Rs0, Rs) reprezentują:
Q0 - the current state (or initial state before the "perform")
Ls0 - the current set of symbols that are LEFT of the head
Ls - the FINAL set of symbols that WILL BE left of the head after perform
Rs0 - the current set of symbols that are RIGHT of the head
Rs - the FINAL set of symbols that WILL BE right of the head after perform
Początkowo nie ma już głowy symbole. Tape0 początkowo zawiera wszystkie symbole po prawej stronie głowy. Aby „uruchomić maszynę”, główny orzecznik wzywa:
perform(Q0, [], Ls, Tape0, Rs)
Zaczyna się od stanu początkowego, Q0, nie ma lewej głowicy zacząć ([]) Symbole i posiada symbole w Tape0 prawej stronie głowa, aby rozpocząć.Oczekuje, że po zakończeniu zapytania zostanie utworzony Ls z końcowym zestawem symboli po lewej stronie głowy i ostatecznym zestawem symboli po prawej stronie głowy.
Cała reszta obsługuje teraz perform/5.
symbol([Sym|Rs], Sym, Rs)
ta określa zależność między listą symboli [Sym|Rs] i pierwszego symbolu w tej listy (Sym) i reszty listy (Rs). perform/5 używa tego predykatu do odczytania następnego symbolu, który znajduje się obecnie na prawo od głowy.
Aby to działało poprawnie w kontekście jest używana, perform/5 orzecznik utrzymuje Rs0 zmienną takie, że jest prawidłowo w celu gdzie szef liście jest pierwszy symbol po prawej, drugi element lista jest następującym symbolem po prawej i tak dalej. Zauważ, że tak nie jest w przypadku listy symboli po lewej stronie. Lista po lewej stronie jest utrzymywana w kolejności w odwrotnej kolejności, w jakiej symbole pojawiają się na taśmie. Powodem jest to, że można je rozpatrywać w kolejności, w jakiej znajdują się one od obecnej pozycji głowy. Więcej na ten temat nieco później.
action(left/stay/right, Ls0, Ls, Rs0, Rs)
To gdzie działanie jest. :) Rola polega na wykonaniu danej akcji i dostarczeniu poprawnie zaktualizowanych list z lewej i prawej strony nowej pozycji głowy po wykonaniu jednej akcji. Ls0 i Rs0 są listami symboli z lewej strony iz prawej, odpowiednio, przed czynność została wykonana. I Ls i Rs są symbolami po lewej stronie iz prawej strony głowicy, odpowiednio, po wykonanie akcji.
action(stay, Ls, Ls, Rs, Rs).
Akcja ta mówi, że gdy Zatrzymuję symbole na lewo i na prawo od głowy się nie zmieniają.
action(right, Ls0, [Sym|Ls0], [Sym|Rs], Rs).
Akcja ta mówi, że kiedy natychmiast przesunąć głowicę prawo pozycję jednego symbolu, do prawej (co jest Sym ponieważ prawo zestaw symboli jest [Sym|Rs]) natychmiast staje się symbolem w lewo. Lewy zestaw symboli pierwotnie był Ls0 i stał się [Sym|Ls0]. Lista symboli po prawej stronie była pierwotnie [Sym|Rs] i stała się Rs.
Działanie jest nieco bardziej skomplikowane niż stay lub right, ponieważ gdy po lewej stronie nie ma symboli, a lewy ruch jest wskazany, głowa nadal przesuwa się w lewo, a po prawej pojawia się pusty znak.Więc left to podzielone na osobnej, małej orzecznika:
action(left, Ls0, Ls, Rs0, Rs) :- left(Ls0, Ls, Rs0, Rs).
left([], [], Rs0, [b|Rs0]).
Tutaj, jeśli lewy zestaw symboli jest pusty ([]), a następnie przesuwając lewo oznacza lewy symbole pozostaje pusta ([]) oraz nowy pusty (b) pojawia się po prawej stronie głowy, na początku oryginalnego zestawu prawych symboli (prawa lista zmienia się z Rs0 na [b|Rs0]).
left([L|Ls], Ls, Rs, [L|Rs]).
Oto niektóre symbole po lewej stronie, a akcja polega na przesunięciu w lewo. Początkowy zestaw symboli po lewej to [L|Ls] (L jest symbolem bezpośrednio po lewej stronie głowy), a początkowy zestaw symboli po prawej stronie głowy to Rs. Po przesunięciu głowicy w lewo, pierwszy symbol po lewej stronie staje się pierwszym symbolem po prawej stronie. Zatem zaktualizowany lewy zestaw symboli to Ls, a zaktualizowany prawy zestaw symboli to [L|Rs].
action(left, ...) orzeczenie mogło być napisane bez orzecznika pomocniczego, left/4, w ten sposób:
action(left, [], [], Rs0, [b|Rs0]).
action(left, [L|Ls], Ls, Rs, [L|Rs]).
Powrót do listy po lewej i oryginalnego turing/2 orzecznika: po turing/2 połączeń perform(q0, [], Ls, Tape0, Rs), ma ostateczny zestaw symbole na prawo (Rs), które są w poprawnej kolejności, od lewej do prawej. Jednak ostateczny zestaw symboli po lewej stronie (Ls) znajduje się na liście od prawej do lewej (ponieważ ich kolejność jest zbliżona do aktualnej pozycji głowy). Dlatego, aby pokazać całą taśmę we właściwej kolejności, lewą listę symboli należy odwrócić, a następnie dodać do właściwego zestawu symboli. W związku z tym wzywa:
reverse(Ls, Ls1),
append(Ls1, Rs, Tape).
Przełamywanie perform/5 predykat:
perform(qf, Ls, Ls, Rs, Rs) :- !.
mówi, że jeśli jesteśmy w stanie końcowym qf, wówczas końcowa lista pozostawionych symboli, Ls, staje się naszym bieżącym zestawem z pozostawionymi symbolami. Podobnie dla właściwych symboli.
perform(Q0, Ls0, Ls, Rs0, Rs) :-
% Read the symbol to the right of the head (Sym)
%
symbol(Rs0, Sym, RsRest),
% Apply first found matching rule to the current state (Q0)
% and the current symbol on the right (Sym), resulting in
% a new symbol (NewSym) and an action (Action)
%
once(rule(Q0, Sym, Q1, NewSym, Action)),
% Perform the action using the current list of symbols on the left (Ls0)
% and the updates list of symbols on the right (old right symbol (Sym)
% replaced by the new right symbol (NewSym), which is [NewSym|RsRest]
% with the action resulting in new left Ls1 and new right Ls2
% sets of symbols
%
action(Action, Ls0, Ls1, [NewSym|RsRest], Rs1),
% Recursively perform the Turing engine on the new state, left,
% and right sets of symbols until we hit the final state (qf)
% with final result being left symbols, Ls, and right symbols, Rs
%
perform(Q1, Ls1, Ls, Rs1, Rs).
Dziękuję bardzo. –