Der Wikipedia Prolog Artikel enthält diesen Turing Machine Simulator:
%Vor%Es gibt ein Beispielprogramm, das:
Programm:
%Vor%Das Programm wird wie folgt ausgeführt:
%Vor%Ich verstehe die Bedeutung einiger Variablennamen in Regeln / Fakten:
turing(Tape0, Tape)
rule(Q0, Sym, Q1, NewSym, Action)
Ich verstehe die Bedeutung der Variablen in diesen Regeln / Fakten nicht:
%Vor%Kann jemand erklären?
In der Turing-Maschine zeigt der Schreibkopf bei jedem gegebenen Zustand auf eine bestimmte Stelle auf dem Band. Es wird Symbole vom Kopf und Symbole rechts vom Kopf geben.
Betrachten wir das erste, Hauptprädikat:
%Vor% Es wird "die Maschine ausführen", indem perform/5 aufgerufen wird. Die Argumente für perform(Q0, Ls0, Ls, Rs0, Rs) stehen für:
Zunächst sind keine Symbole mehr vom Kopf übrig. Tape0 enthält zunächst alle Symbole rechts vom Kopf. Um "die Maschine auszuführen", ruft das Hauptprädikat auf:
Es beginnt mit dem Anfangszustand, Q0 , hat keine Symbole mehr vom Anfang ( [] ) und hat die Symbole in Tape0 rechts vom Anfang des Kopfes. Nach Abschluss der Abfrage wird erwartet, dass Ls mit dem letzten Satz von Symbolen links vom Kopf und Rs mit dem letzten Satz von Symbolen rechts vom Kopf instanziiert ist.
Alles andere unterstützt jetzt perform/5 .
Dies definiert eine Beziehung zwischen der Liste der Symbole [Sym|Rs] und dem ersten Symbol in dieser Liste ( Sym ) und dem 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 im Kontext, in dem es verwendet wird, korrekt funktioniert, behält das Prädikat perform/5 die Variable Rs0 so bei, dass sie korrekt in der Reihenfolge ist, wobei der Kopf der Liste das erste Symbol ist Rechts ist das zweite Element der Liste 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 umgekehrter Reihenfolge beibehalten, wie die Symbole auf dem Band erscheinen. Der Grund dafür ist, dass sie in der Reihenfolge der verbleibenden Position der aktuellen Kopfposition betrachtet werden können. Mehr dazu später.
Hier ist die Aktion . :) 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. bevor die Aktion ausgeführt wird. Und Ls und Rs sind die Symbole links und rechts des Kopfes bzw. nachdem die Aktion ausgeführt wurde.
Diese Aktion besagt, dass, wenn ich bleibe , die Symbole links und rechts vom Kopf sich nicht ändern.
%Vor% Diese Aktion besagt, dass, wenn ich den Kopf rechts um eine Symbolposition bewege, das Symbol sofort nach rechts ( Sym seit rechts <) / em> Satz von Symbolen ist [Sym|Rs] ) wird das Symbol sofort nach links. Die linke Gruppe 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 Aktion left wird ein wenig komplizierter als stay oder right , denn wenn links keine Symbole mehr vorhanden sind und eine Bewegung nach links angezeigt wird, bewegt sich der Kopf immer noch nach links und rechts erscheint ein Leerzeichen . Also left ist in ein separates, kleines Prädikat aufgeteilt:
Wenn die linke Gruppe von Symbolen leer ist ( [] ), bedeutet das Verschieben links , dass die linken Symbole leer bleiben ( [] ) und ein neues Leerzeichen ( b ) erscheint auf der rechten Seite des Kopfes, an der Spitze des ursprünglichen Satzes von rechten Symbolen (die rechte Liste ändert sich von Rs0 nach [b|Rs0] ).
Hier sind einige Symbole auf der linken Seite und die Aktion ist nach links zu bewegen. Die erste Gruppe von Symbolen links ist [L|Ls] ( L ist das Symbol unmittelbar links vom Kopf) und die erste Gruppe von Symbolen rechts vom Kopf sind Rs . Wenn sich der Kopf links bewegt, wird das erste Symbol auf der linken Seite zum ersten Symbol auf der rechten Seite. Also ist der aktualisierte linke Satz von Symbolen Ls und der aktualisierte rechte Satz von Symbolen ist [L|Rs] .
Das Prädikat action(left, ...) hätte ohne das Hilfsprädikat left/4 geschrieben werden können:
Zurück zur linken Liste und zum ursprünglichen turing/2 -Prädikat: nachdem turing/2 Aufrufe perform(q0, [], Ls, Tape0, Rs) aufgerufen hat, hat es eine letzte Menge von Symbolen auf dem rechts ( Rs ), die darin enthalten sind die richtige Reihenfolge, von links nach rechts. Die letzte Gruppe von Symbolen auf der linken Seite ( Ls ) wird 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. Also die Anrufe:
Zerlegen des perform/5 Prädikats:
Dies besagt, dass, wenn wir uns im Endstatus qf befinden, die letzte Liste der linken Symbole, Ls , zu unserer aktuellen Menge von
Tags und Links prolog turing-machines