Post–Turing-Maschine - Post–Turing machine

Ein Post-Turing Maschine ist eine „Programm Formulierung“ eine Art von Turing Maschine , eine Variante , umfassend Emil Beitrag ist Turing-Äquivalent - Modell der Berechnung . Das Modell von Post und das Modell von Turing, obwohl sie einander sehr ähnlich sind, wurden unabhängig voneinander entwickelt. Turings Papier wurde im Mai 1936 zur Veröffentlichung eingereicht, gefolgt von Posts im Oktober.) Eine Post-Turing-Maschine verwendet ein binäres Alphabet , eine unendliche Folge von binären Speicherplätzen und eine primitive Programmiersprache mit Anweisungen für die bidirektionale Bewegung zwischen den Speichern Standorte und Änderung ihres Inhalts nacheinander. Die Bezeichnungen „Post–Turing-Programm“ und „Post–Turing-Maschine“ wurden 1973–1974 von Martin Davis verwendet (Davis 1973, S. 69ff). Später im Jahr 1980 verwendete Davis den Namen "Turing-Post-Programm" (Davis, in Steen S. 241).

1936: Postmodell

In seiner 1936 erschienenen Arbeit „Finite Combinatory Processes – Formulation 1“ beschrieb Emil Post ein Modell, von dem er vermutete, dass es „ logisch äquivalent zur Rekursivität “ sei.

Das Berechnungsmodell von Post unterscheidet sich vom Turing-Maschinenmodell durch eine weitere "Atomisierung" der Handlungen, die ein menschlicher "Computer" während einer Berechnung ausführen würde.

Das Modell von Post verwendet einen " Symbolraum ", der aus einer "zweifachen unendlichen Folge von Leerzeichen oder Kästchen" besteht, wobei jeder Kasten in einer von zwei möglichen Zuständen sein kann, nämlich "markiert" (wie durch einen einzelnen vertikalen Strich) und "unmarkiert". " (leer). Anfänglich, endlich - viele der Kästen sind markiert, der Rest ist unmarkiert. Ein "Arbeiter" soll sich dann zwischen den Boxen bewegen, wobei er sich in jeweils nur einer Box befindet und in ihr arbeitet, gemäß einem festen endlichen "Satz von Anweisungen" ( Anweisungen ), die der Reihe nach nummeriert sind (1,2,3, ..., n. ). Beginnend bei einem Kästchen "als Ausgangspunkt herausgegriffen" hat der Arbeiter nacheinander die Anweisungen zu befolgen, beginnend mit der Anweisung 1.

Es gibt fünf verschiedene primitive Operationen, die der Arbeiter ausführen kann:

(a) Markieren der Box, in der sie sich befindet, wenn sie leer ist

(b) Löschen der Markierung in der Box, in der sie sich befindet, wenn sie markiert ist

(c) Bewegen Sie sich in die Box rechts davon

(d) Bewegen Sie sich in die Box auf der linken Seite

(e) Feststellen, ob die Box, in der es sich befindet, markiert ist oder nicht.

Dann muss die i- ^te "Anweisung" (Anweisung) an den Arbeiter eine der folgenden Formen sein:

(Der obige eingerückte Text und die Kursivschrift sind wie im Original.) Post bemerkt, dass sich diese Formulierung "in den Anfangsstadien" der Entwicklung befindet, und erwähnt mehrere Möglichkeiten für "größere Flexibilität" in ihrer endgültigen "endgültigen Form", einschließlich

1. Ersetzen der Unendlichkeit von Kästchen durch einen endlichen erweiterbaren Symbolraum, "Erweitern der primitiven Operationen, um die notwendige Erweiterung des gegebenen endlichen Symbolraums im Verlauf des Prozesses zu ermöglichen",
2. ein Alphabet mit mehr als zwei Symbolen verwenden, "mehr als eine Möglichkeit haben, ein Kästchen zu markieren",
3. Einführung endlich-vieler "physischer Objekte, die als Zeiger dienen, die der Arbeiter identifizieren und von Box zu Box bewegen kann".

1947: Post formelle Reduktion der Turing-5-Tupel auf 4-Tupel

Wie in dem Artikel Turing-Maschine kurz erwähnt , hat Post in seinem Aufsatz von 1947 ( Recursive Unsolvability of a Problem of Thue ) die Turing-5-Tupel zu 4-Tupeln atomisiert:

"Unsere Quadruplets sind Quintuplets in der Turing-Entwicklung. Das heißt, wo unsere Standardanweisung entweder ein Drucken (Überdrucken) oder eine Bewegung nach links oder rechts anordnet, ordnet Turings Standardanweisung immer ein Drucken und eine Bewegung an, rechts, links oder keine" ( Fußnote 12, Unentscheidbar , S. 300)

Wie Turing definierte er das Löschen als das Drucken eines Symbols "S0". Und so ließ sein Modell nur Vierlinge von drei Typen zu (vgl. Undecidable , S. 294):

q _i S _j L q _l ,

q _i S _j R q _l ,

q _i S _j S _k q _l

Zu diesem Zeitpunkt hielt er noch an der Turing-State-Machine-Konvention fest – er hatte die Vorstellung einer angenommenen sequentiellen Ausführung von Schritten erst dann formalisiert, wenn ein bestimmter Test eines Symbols die Ausführung an anderer Stelle „verzweigte“.

1954, 1957: Wang-Modell

Für eine noch weitere Reduzierung – auf nur vier Anweisungen – des hier vorgestellten Wang-Modells siehe Wang B-Maschine .

Wang (1957, aber 1954 der ACM vorgestellt) wird oft als Quelle für die "Programmformulierung" von Binärband-Turingmaschinen mit nummerierten Anweisungen aus der Menge angeführt (vgl. Minsky (1967), S. 200).

schreibe 0

schreibe 1

geh nach links

nach rechts bewegen

wenn 0 gescannt wird, dann gehe zu Anweisung i

wenn 1 gescannt wird, dann gehe zu Anweisung j

Jede Binärband-Turing-Maschine wird unter Verwendung der obigen Anweisungen leicht in ein äquivalentes "Wang-Programm" umgewandelt.

1974: erstes Davis-Modell

Martin Davis war ein Student Schüler von Emil Post. Zusammen mit Stephen Kleene absolvierte er seinen Ph.D. unter Alonzo Church (Davis (2000) 1. und 2. Fußnoten S. 188).

Das folgende Modell präsentierte er 1973–1974 in einer Reihe von Vorträgen vor dem Courant Institute an der NYU. Dies ist das Modell, auf das Davis mit seiner "Post-Turing-Sprache" offiziell den Namen "Post-Turing-Maschine" angewendet hat. Es wird davon ausgegangen, dass die Anweisungen sequentiell ausgeführt werden (Davis 1974, S. 71):

1978: zweites Davis-Modell

Das folgende Modell erscheint als Aufsatz Was ist eine Berechnung? in Steen, Seiten 241–267. Aus irgendeinem Grund hat Davis sein Modell in "Turing-Post-Maschine" umbenannt (mit einer Rückseite auf Seite 256).

Im folgenden Modell weist Davis dem „Mark/Slash“ von Post die Zahlen „1“ und dem leeren Quadrat „0“ zu. Um Davis zu zitieren: „Wir sind jetzt bereit, die Turing-Post-Programmiersprache einzuführen. In dieser Sprache gibt es sieben Arten von Anweisungen:

"DRUCKEN 1

"DRUCKEN 0

"GEH RECHTS

"GEHE NACH LINKS

"GEHEN SIE ZU SCHRITT i, WENN 1 GESCANNT WIRD

"GEHEN SIE ZU SCHRITT i, WENN 0 GESCANNT WIRD

"HALT

"Ein Turing-Post-Programm ist dann eine Liste von Anweisungen, von denen jede einer dieser sieben Arten entspricht. Natürlich muss in einem tatsächlichen Programm der Buchstabe i in einem Schritt der fünften oder sechsten Art durch a ersetzt werden bestimmte (positive ganze) Zahl." (Davis in Steen, S. 247).

1994 (2. Auflage): Davis–Sigal–Weyukers Post–Turing-Programmmodell

"Obwohl die von uns vorgestellte Formulierung von Turing im Geiste der ursprünglich von Emil Post gegebenen näher kommt, war es Turings Analyse der Berechnung, die diese Formulierung so passend erscheinen ließ. Diese Sprache hat eine grundlegende Rolle in der theoretischen Informatik gespielt." (Davis et al. (1994) S. 129)

Dieses Modell ermöglicht das Drucken mehrerer Symbole. Das Modell ermöglicht B (leer) anstelle von S ₀ . Das Band ist in beide Richtungen unendlich. Entweder der Kopf oder das Band bewegt sich, aber ihre Definitionen von RIGHT und LEFT geben in beiden Fällen immer das gleiche Ergebnis an (Turing verwendet dieselbe Konvention).

DRUCKEN σ ;Gescanntes Symbol durch σ . ersetzen

IF σ GOTO L ;IF das gescannte Symbol ist σ THEN gehe zu "der ersten" Anweisung mit der Bezeichnung L

RECHTS ;Quadrat direkt rechts neben dem gerade gescannten Quadrat scannen

LINKS ;Quadrat direkt links vom gerade gescannten Quadrat scannen

Dieses Modell reduziert sich auf die oben vorgestellten binären { 0, 1 }-Versionen, wie hier gezeigt:

DRUCKEN 0 = LÖSCHEN ;Gescanntes Symbol ersetzen durch 0 = B = BLANK

PRINT 1 ;Ersetzen Sie das gescannte Symbol durch 1

IF 0 GOTO L ;WENN das gescannte Symbol 0 ist DANN gehe zum "ersten" Befehl mit der Bezeichnung L

IF 1 GOTO L ;WENN das gescannte Symbol 1 ist DANN gehe zum "ersten" Befehl mit der Bezeichnung L

RECHTS ;Quadrat direkt rechts neben dem gerade gescannten Quadrat scannen

LINKS ;Quadrat direkt links vom gerade gescannten Quadrat scannen

Beispiele der Post–Turing-Maschine

Zerstäubung von Turing-Fünfteln in eine Folge von Post-Turing-Anweisungen

Die folgende "Reduktion" (Zerlegung, Zerstäubung) Methode – von 2-Symbol Turing 5-Tupel zu einer Folge von 2-Symbol Post–Turing Anweisungen – findet sich in Minsky (1961). Er stellt fest, dass diese Reduktion auf "ein Programm ... eine Folge von Anweisungen " im Geiste der B-Maschine von Hao Wang liegt (kursiv im Original, vgl. Minsky (1961) S. 439).

(Minskys Reduktion auf das, was er "eine Unterroutine" nennt, führt zu 5 statt 7 Post-Turing-Anweisungen. Er hat Wi0 nicht atomisiert: "Schreibe Symbol Si0; gehe in den neuen Zustand Mi0" und Wi1: "Schreibe Symbol Si1; go to new state Mi1". Die folgende Methode zerstäubt Wi0 und Wi1 weiter; ansonsten sind die Methoden identisch.)

Diese Reduktion von Turing-5-Tupeln auf Post-Turing-Anweisungen führt möglicherweise nicht zu einem "effizienten" Post-Turing-Programm, aber es wird dem ursprünglichen Turing-Programm treu bleiben.

Im folgenden Beispiel wandelt sich jedes Turing-5-Tupel des 2-State- Busy-Bibers in

für insgesamt 1 + 2 + 1 + 2 + 1 = 7 Anweisungen pro Turing-Zustand.

Der Turing-Zustand "A" des 2-State-Busy-Bibers, geschrieben als zwei Zeilen von 5-Tupeln, lautet beispielsweise:

Die Tabelle stellt nur eine einzelne Turing-"Anweisung" dar, aber wir sehen, dass sie aus zwei Zeilen mit 5-Tupeln besteht, eine für den Fall "Bandsymbol unter Kopf = 1", die andere für den Fall "Bandsymbol unter Kopf = 0 ". Turing beobachtete ( Undecidable , S. 119), dass die linken beiden Spalten – „m-Konfiguration“ und „Symbol“ – die aktuelle „Konfiguration“ der Maschine darstellen – ihren Zustand einschließlich Band und Tabelle zu diesem Zeitpunkt – und die letzten drei Spalten sind sein späteres "Verhalten". Da sich die Maschine nicht in zwei "Zuständen" gleichzeitig befinden kann, muss die Maschine entweder in die eine oder andere Konfiguration "verzweigen":

Nach dem „Konfigurationszweig“ (J1 xxx) bzw. (J0 xxx) folgt die Maschine einem der beiden nachfolgenden „Verhalten“. Wir listen diese beiden Verhaltensweisen in einer Zeile auf und nummerieren (oder beschriften) sie der Reihe nach (eindeutig). Unter jedem Sprung (Zweig, Gehe zu) platzieren wir seine Sprung-zu-"Nummer" (Adresse, Ort):

Gemäß den Konventionen der Post-Turing-Maschine bestehen die Anweisungen Drucken, Löschen, Links und Rechts jeweils aus zwei Aktionen:

Und gemäß den Konventionen der Post-Turing-Maschine bestehen die bedingten "Sprünge" J0xxx, J1xxx aus zwei Aktionen:

Und gemäß den Konventionen der Post-Turing-Maschine besteht der unbedingte "Sprung" Jxxx aus einer einzelnen Aktion, oder wenn wir die 2-Aktions-Sequenz regulieren wollen:

Welche und wie viele Sprünge sind notwendig? Der unbedingte Sprung J xxx ist einfach J0 gefolgt von J1 (oder umgekehrt). Wang (1957) zeigt auch, dass nur ein bedingter Sprung erforderlich ist, dh entweder J0 xxx oder J1 xxx. Mit dieser Einschränkung wird es jedoch schwierig, für die Maschine Anweisungen zu schreiben. Oft werden nur zwei verwendet, dh

aber die Verwendung aller drei { J0 xxx, J1 xxx, J xxx } eliminiert zusätzliche Anweisungen. In dem 2-State Busy Beaver-Beispiel verwenden wir nur { J1 xxx, J xxx }.

2-State beschäftigt Biber

Die Mission des fleißigen Bibers ist es, so viele wie möglich zu drucken, bevor er anhält. Die Anweisung "Print" schreibt eine 1, die Anweisung "Erase" (in diesem Beispiel nicht verwendet) schreibt eine 0 (dh sie entspricht P0). Das Band bewegt sich "links" oder "rechts" (dh der "Kopf" steht still).

Zustandstabelle für einen beschäftigten Biber mit einer Turing-Maschine mit zwei Zuständen :

Anweisungen für die Post-Turing-Version eines 2-State-Busy-Bibers: Beachten Sie, dass sich alle Anweisungen in derselben Zeile und nacheinander befinden. Dies ist eine deutliche Abweichung von der "Turing"-Version und hat das gleiche Format wie ein sogenanntes "Computerprogramm":

Alternativ können wir die Tabelle als String schreiben. Die Verwendung von "Parameter-Trennzeichen" ":" und Instruktions-Trennzeichen "," sind ausschließlich unsere Wahl und erscheinen nicht im Modell. Es gibt keine Konventionen (aber siehe Booth (1967) S. 374 und Boolos und Jeffrey (1974, 1999) S. 23) für einige nützliche Ideen, wie man Zustandsdiagramm-Konventionen mit den Anweisungen kombinieren kann – dh Pfeile verwenden, um anzuzeigen das Ziel der Sprünge). Im unmittelbar folgenden Beispiel sind die Anweisungen beginnend mit "1" sequentiell , und die Parameter/"Operanden" werden als Teil ihrer Anweisungen/"Opcodes" betrachtet:

J1:5, P, R, J:8, P, L, J:8, J1:12, P, L, J1:1, P, N, J:15, H

Das Zustandsdiagramm eines beschäftigten Bibers mit zwei Zuständen (kleine Zeichnung, rechte Ecke) wird in die entsprechende Post-Turing-Maschine umgewandelt, wobei 7 Post-Turing-Anweisungen pro "Turing"-Zustand ersetzt werden.

Der HALT-Befehl fügt den 15. Zustand hinzu.

Ein "Lauf" des 2-State-Busy-Bibers mit allen Zwischenschritten der gezeigten Post-Turing-Maschine.

Anmerkungen

Verweise

• Stephen C. Kleene , Introduction to Meta-Mathematics, North-Holland Publishing Company , New York, 10. Auflage 1991, Erstveröffentlichung 1952. Kapitel XIII ist eine ausgezeichnete Beschreibung von Turing-Maschinen; Kleene verwendet in seiner Beschreibung ein Post-ähnliches Modell und gibt zu, dass das Turing-Modell weiter atomisiert werden könnte, siehe Fußnote 1.
• Martin Davis , Herausgeber: The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions , Raven Press, New York, 1965. Zu den Veröffentlichungen gehören die von Gödel , Church , Rosser , Kleene und Post.
• Martin Davis , "Was ist eine Berechnung", in Mathematics Today , Lynn Arthur Steen, Vintage Books (Random House), 1980. Ein wunderbares kleines Papier, vielleicht das beste, das jemals über Turing-Maschinen geschrieben wurde. Davis reduziert die Turing-Maschine auf ein viel einfacheres Modell, das auf Posts Berechnungsmodell basiert. Enthält eine kleine Biographie von Emil Post.
• Martin Davis , Computability: with Notes by Barry Jacobs , Courant Institute of Mathematical Sciences, New York University, 1974.
• Martin Davis , Ron Sigal , Elaine J. Weyuker , (1994) Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science – 2. Auflage , Academic Press: Harcourt, Brace & Company, San Diego, 1994 ISBN  0-12-206382- 1 (Erste Ausgabe, 1983).
• Fred Hennie , Einführung in die Berechenbarkeit , Addison-Wesley, 1977.
• Marvin Minsky , (1961), Recursive Unsolvability of Post's problem of 'Tag' and other Topics in Theory of Turing Machines , Annals of Mathematics, Bd. 74, Nr. 3, November 1961.
• Roger Penrose , The Emperor's New Mind: Concerning Computers, Minds and the Laws of Physics , Oxford University Press, Oxford England, 1990 (mit Korrekturen). Vgl. Kapitel 2, "Algorithmen und Turing-Maschinen". Eine überkomplizierte Präsentation (siehe Davis' Papier für ein besseres Modell), aber eine gründliche Präsentation von Turing-Maschinen und dem Halteproblem sowie Churchs Lambda-Kalkül .
• Hao Wang (1957): „Eine Variante zu Turings Theorie der Rechenmaschinen“, Journal of the Association for Computing Machinery (JACM) 4, 63–92.