In der Turing-Maschine zeigt der Schreibkopf in einem bestimmten Zustand auf eine bestimmte Stelle auf dem Band. Es wird Symbole vom Kopf und Symbole rechts vom Kopf geben.
Mit Blick auf dem ersten, Haupt Prädikat:
turing(Tape0, Tape) :-
perform(q0, [], Ls, Tape0, Rs),
reverse(Ls, Ls1),
append(Ls1, Rs, Tape).
Es wird „die Maschine läuft“ von perform/5 aufrufen. Die Argumente für perform(Q0, Ls0, Ls, Rs0, Rs) darstellen:
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
Zu Beginn gibt es keine Symbole des Kopfes nach links. Tape0 enthält zunächst alle Symbole rechts vom Kopf. Um „die Maschine laufen“, ruft das Haupt Prädikat:
perform(Q0, [], Ls, Tape0, Rs)
Es beginnt mit dem Anfangszustand, Q0, hat keine Symbole des Kopfes nach links mit ([]) zu beginnen und hat die Symbole in Tape0 rechts von der Kopf um zu beginnen.Nach Abschluss der Abfrage wird erwartet, dass Ls instanziiert ist mit dem letzten Satz von Symbolen links vom Kopf und Rs der letzte Satz von Symbolen rechts vom Kopf.
Alles andere unterstützt jetzt perform/5.
symbol([Sym|Rs], Sym, Rs)
Dies definiert eine Beziehung zwischen der Liste von Symbolen [Sym|Rs], und dem ersten Symbol in der Liste (Sym) und der Rest der Liste (Rs). perform/5 verwendet dieses Prädikat, um das nächste Symbol zu lesen, das sich derzeit rechts vom Kopf befindet.
Damit dies korrekt im Rahmen arbeiten, um es verwendet wird, behält die perform/5 Prädikat die Rs0 Variable, so daß es richtig ist, um, wo der Kopf der Liste das erste Symbol auf der rechten Seite ist, das zweite Element von Die Liste ist das folgende Symbol auf der rechten Seite und so weiter. Beachten Sie, dass dies nicht der Fall der Liste der Symbole auf der linken Seite ist. Die Liste auf der linken Seite wird in umgekehrt Reihenfolge der Symbole auf dem Band angezeigt. Der Grund dafür ist, dass sie in der Reihenfolge der verbleibenden Position der aktuellen Kopfposition betrachtet werden können. Mehr dazu später.
action(left/stay/right, Ls0, Ls, Rs0, Rs)
Hier wird die Aktion ist. :) Es ist die Aufgabe, die gegebene Aktion auszuführen und die korrekt aktualisierten Listen darüber zu liefern, was links und rechts von der neuen Kopfposition ist, nachdem diese eine Aktion ausgeführt wurde. Ls0 und Rs0 sind die Listen der Symbole links und rechts des Kopfes bzw. vor die Aktion durchgeführt wird. Und Ls und Rs sind die Symbole links und rechts des Kopfes bzw. nach die Aktion durchgeführt wird.
action(stay, Ls, Ls, Rs, Rs).
Aktion sagt, dass, wenn ich, die Symbole auf der linken Seite und auf der rechten Seite des Kopfes nicht ändern bleiben .
action(right, Ls0, [Sym|Ls0], [Sym|Rs], Rs).
Aktion sagt, dass, wenn ich Sie den Kopf rechts einer Symbolposition, das Symbol sofort dem rechts (die Sym ist, da die rechten Satz von Symbolen ist [Sym|Rs]) unmittelbar das Symbol wird nach links. Der linke Satz von Symbolen war ursprünglich Ls0 und wird [Sym|Ls0]. Die Liste der Symbole auf der rechten Seite war ursprünglich [Sym|Rs] und wird Rs.
Die left Aktion ein wenig komplizierter wird als stay oder right, weil, wenn es keine weiteren Symbole auf der linken Seite und einer Bewegung links sind angezeigt wird, bewegt sich der Kopf noch links und eine leere erscheint auf der rechten Seite.So left ist es ausgebrochen in ein separates, kleines Prädikat:
action(left, Ls0, Ls, Rs0, Rs) :- left(Ls0, Ls, Rs0, Rs).
left([], [], Rs0, [b|Rs0]).
Wenn hier die links von Symbolen eingestellt ist leer ([]), dann bewegen links bedeutet, dass die linken Symbole leer bleiben ([]) und ein Eine neue Leerstelle (b) erscheint auf der rechten Seite des Kopfes, am Anfang der ursprünglichen Gruppe von rechten Symbolen (die rechte Liste ändert sich von Rs0 zu [b|Rs0]).
left([L|Ls], Ls, Rs, [L|Rs]).
Hier sind einige Symbole auf der linken Seite und die Aktion ist nach links zu bewegen. Die erste Gruppe von Symbolen auf der linken Seite ist [L|Ls] (L ist das Symbol unmittelbar links vom Kopf) und die erste Reihe von Symbolen rechts vom Kopf sind Rs. Wenn sich der Kopf bewegt links, dann wird das erste Symbol auf der linken Seite das erste Symbol auf der rechten Seite. Der aktualisierte linke Satz von Symbolen ist also Ls und der aktualisierte rechte Satz von Symbolen ist [L|Rs].
Das action(left, ...) Prädikat ohne Hilfs Prädikat geschrieben worden sein könnte, left/4, auf diese Weise:
action(left, [], [], Rs0, [b|Rs0]).
action(left, [L|Ls], Ls, Rs, [L|Rs]).
Zurück zur linken Liste und das ursprünglichen turing/2 Prädikat: nach turing/2 Anrufen perform(q0, [], Ls, Tape0, Rs), hat es einen letzten Satz von Symbole auf der rechts (Rs), die in der richtigen Reihenfolge sind, von links nach rechts. Die letzten Symbole auf der linken Seite (Ls) werden jedoch von rechts nach links aufgelistet (da sie in der Reihenfolge ihrer Nähe zur aktuellen Kopfposition sind). Um das gesamte Band in der richtigen Reihenfolge zu zeigen, muss daher die linke Liste von Symbolen umgekehrt und dann der richtigen Menge von Symbolen vorangestellt werden. Somit werden die Anrufe:
reverse(Ls, Ls1),
append(Ls1, Rs, Tape).
Aufbrechen der perform/5 Prädikat:
perform(qf, Ls, Ls, Rs, Rs) :- !.
Dies sagt, dass, wenn wir im Endzustand sind qf, dann ist die letzte Liste von links Symbole, Ls, wird unser aktueller Satz links Symbole. Ähnlich für die richtigen Symbole.
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).
Vielen Dank. –