Ist das Konzept der Turingmaschine von Automaten abgeleitet?

Ich hatte erst kürzlich eine Diskussion über Turingmaschinen, als ich gefragt wurde: "Ist die Turingmaschine von Automaten abgeleitet, oder ist es umgekehrt?"

Ich wusste die Antwort natürlich nicht, aber ich bin neugierig, es herauszufinden. Die Turing-Maschine ist im Grunde eine etwas ausgefeiltere Version eines Push-Down-Automaten. Ich würde davon ausgehen, dass die Turing-Maschine von Automaten abgeleitet wurde, aber ich habe keine endgültigen Beweise oder Erklärungen. Ich könnte einfach falsch liegen ... vielleicht wurden sie isoliert entwickelt.

Bitte! Befreie diesen Geist von ewigen Tangenten der Verstrickung.

Weder!

Der beste Weg, diese Unabhängigkeit zu erkennen, ist das Lesen der Originalarbeiten .

• Turings Papier von 1936, in dem Turing-Maschinen vorgestellt werden, bezieht sich nicht auf einen einfacheren Typ eines (abstrakten) endlichen Automaten.

• McCulloch und Pitts '1943er Aufsatz, in dem "Nerven-Netze" vorgestellt wurden, die Vorläufer moderner endlicher Maschinen, schlugen sie als vereinfachte Modelle neuronaler Aktivität vor, nicht als Berechnung an sich.

Eine interessante frühe Perspektive bietet die Umfrage von Claude Shannon von 1953 , die einen vollständigen Abschnitt über Turing-Maschinen enthält, jedoch nichts über endliche Automaten aussagt, wie wir sie heute erkennen würden (obwohl er Kleenes Bericht von 1951 zitiert).

Moderne endliche Automaten beginnen wohl mit einer Veröffentlichung von Kleene aus dem Jahr 1956 , die ursprünglich als RAND-Fachbericht aus dem Jahr 1951 veröffentlicht wurde und reguläre Ausdrücke definierte. Kleene war sich sicherlich der Ergebnisse von Turing bewusst, da er ähnliche Ergebnisse selbst (in der Sprache der primitiven rekursiven Funktionen) fast zur gleichen Zeit veröffentlicht hatte. Trotzdem ist Kleenes einziger Hinweis auf Turing die Erklärung, dass Turing-Maschinen aufgrund ihrer unbegrenzten Bänder keine endlichen Automaten sind. Es ist natürlich möglich, dass Kleenes Denken von Turings Abstraktion beeinflusst wurde, aber Kleenes Definitionen scheinen (für mich) unabhängig zu sein.

In dem von Shannon und McCarthy herausgegebenen Umfrageband von 1956 , in dem sowohl Kleenes Aufsatz über reguläre Expersionen als auch Moores Aufsatz über endliche Wandler veröffentlicht wurden, wurden endliche Automaten und Turing-Maschinen nebeneinander, aber fast unabhängig voneinander diskutiert. Moore zitiert auch Turing, aber nur in einer Fußnote, die besagt, dass Turing-Maschinen keine endlichen Automaten sind.

( Ein kürzlich veröffentlichter Artikel von Kline berichtet über die stürmische Geschichte dieses Bandes und die damit verbundene Dartmouth-Konferenz, die manchmal als "Geburtsort der KI" bezeichnet wird.)

(Eine noch frühere Version von neuronalen Netzen findet sich in Turings Arbeit über "Maschinen des Typs B", wie in dem Buch "Das wesentliche Turing" von etwa 1937 abgedruckt. Ich denke, es scheint, dass viele Leute mit der Idee auf der "Turing" spielten Zeit, da auch heute noch viele CS-Studenten glauben, sie hätten es irgendwann in ihrem Studium "erfunden", bevor sie seine Geschichte entdeckten.)

Sie erwähnen PDAs ausdrücklich. Beachten Sie, dass eine Turing-Maschine einem PDA mit zwei Stapeln entspricht. Die ursprüngliche Begründung von PDAs scheint eng mit der Entwicklung der "Sprachtheorie" ala chomsky verwandt gewesen zu sein.

siehe zB Syntactic Analysis und Pushdown Store, "Proceedings of Symposia in Applied Mathematics" (Band 12). Providence, RI: American Mathematical Society, 1961

Dies ist eine der frühesten Referenzen, die ich von Oettinger, "Automatische syntaktische Analyse und der Pushdown-Speicher", S. 104 gesehen habe. Ich weiß nicht, ob es frühere Referenzen für den PDA gibt.

Es dauerte viele Jahre des Studiums aller miteinander verbundenen Automaten, um eine einheitliche Theorie zu entwickeln (die sich noch in der Konstruktion befindet). Die Turing-Gesamtkonzepte wurden gegen Ende der 30er Jahre entwickelt, als sich herausstellte, dass die Lambda-Rechnung (von Church unabhängig entwickelt) Turing-Maschinen entsprach und die Entsprechung zu Post-Maschinen ungefähr zur gleichen Zeit gezeigt wurde (obwohl diese 3 Modelle etwas erfunden wurden) unabhängig & nicht sofort als gleichwertig zu ihrer ursprünglichen Konstruktion erkannt).

Es werden immer noch neue Modelle entwickelt, z. B. Cellular Automata haben eine viel jüngere Geschichte und es hat sich gezeigt, dass sie in verschiedener Hinsicht vollständig sind.

Man kann mit Recht behaupten, dass die meisten Informatiker mit Turings wegweisendem Papier von 1936 vertraut waren und alle späteren Formulierungen von Automatenkonstruktionen (insbesondere das von Turing eingeführte Konzept der Zustandsübergangstabelle) stark beeinflussten.

Nur zum Teufel:

Was war für Sie rückblickend die Bedeutung von Turings Entscheidungspapier von 1936?

Ich hatte immer das Gefühl, dass die Leute gerne ein Lied machen und tanzen. So etwas wie die Trinitätslehre, bei der einem Ingenieur nur die Idee des gespeicherten Programms mitgeteilt werden muss und man sofort sagt: "Das ist absolut erstklassig, so geht das." Das war alles was es zu wissen gab.

In diesem Papier gab es keinen Unterschied, der irgendeine praktische Bedeutung hatte. Er hatte das Glück, dass es überhaupt veröffentlicht wurde, aber ich bin sehr froh, dass er es getan hat. Ich meine, [Alonzo] Churchl hatte das gleiche Ergebnis mit anderen Methoden erzielt.

Ich mochte Turing; Ich meine, wir haben uns sehr gut verstanden. Er legte gern das Gesetz fest und das hat ihn mir nicht gefallen, aber er und ich verstanden uns ganz gut. Die Leute sagen manchmal, dass ich mit Turing nicht klar gekommen bin, aber es ist einfach nicht wahr. Aber dann habe ich sehr darauf geachtet, mich nicht einzumischen.

Maurice Wilkes. http://cacm.acm.org/magazines/2009/9/38898-an-interview-with-maurice-wilkes/fulltext