Historische Gründe für die Einführung von Turing Machine als primäres Berechnungsmodell.

Ich verstehe, dass Turings Modell zum "Standard" bei der Beschreibung von Berechnungen geworden ist. Ich möchte wissen, warum dies der Fall ist - das heißt, warum das TM-Modell weit verbreiteter ist als andere theoretisch äquivalente Modelle (meines Wissens nach), zum Beispiel Kleenes μ-Rekursion oder der Lambda-Kalkül (ich verstehe) dass erstere erst später aufgetaucht sind und letztere ursprünglich nicht speziell als Berechnungsmodell entworfen wurden, aber es zeigt, dass von Anfang an Alternativen bestanden haben).

Ich kann mir nur vorstellen, dass das TM-Modell die Computer, die wir tatsächlich haben, besser repräsentiert als die Alternativen. Ist das der einzige Grund?

Dies scheint im Kontext (einiger Bereiche) der Informatik zuzutreffen, jedoch nicht generell.

Ein Grund hat mit der These der Kirche zu tun. Der Hauptgrund dafür ist, dass einige Experten wie Godel nicht der Meinung waren, dass die Argumente, mit denen frühere / andere Rechenmodelle genau das intuitive Rechenkonzept erfassen, überzeugend sind. Church hatte verschiedene Argumente, die Godel jedoch nicht überzeugten. Auf der anderen Seite Turings Analyse wurde überzeugend für Gödel so als angenommen wurde das Modell für eine effektive Berechnung. Die Äquivalenzen zwischen verschiedenen Modellen werden später bewiesen (glaube ich von Kleene).

$\lambda$$\mu$

$\mu$$\lambda$. Siehe auch diese Papiere von Viggo Stoltenberg-Hansen und John V. Tucker I , II .)

Einige Ressourcen für die weitere Lektüre:

Robert I. Soare hat eine Reihe von Artikeln über die Geschichte dieser Entwicklungen, ich persönlich mag die im Handbuch der Berechenbarkeitstheorie. Weitere Informationen finden Sie in den Referenzen in diesem Dokument.

Eine weitere gute Ressource ist Neil Immermans Artikel zur Berechnungsfähigkeit von SEP, siehe auch den Artikel zur Church-Turing-These von B. Jack Copeland.

Gödels gesammelte Werke enthalten viele Informationen zu seinen Ansichten. Speziell Einführungen in seine Artikel sind äußerst gut geschrieben.

Kleenes " Metamathematik " ist ein sehr schönes Buch.

Wenn Sie immer noch nicht zufrieden sind, überprüfen Sie die Archive der FOM-Mailingliste. Wenn Sie im Archiv keine Antwort finden, senden Sie eine E-Mail an die Mailingliste.

Ich möchte die Behauptung, dass TMs das primäre Berechnungsmodell sind, schwächen oder zumindest auf eine andere Dimension der Frage hinweisen. Es ist klar, dass TMs in den komplexeren und algorithmisch orientierten Teilen der Informatik dominieren, in Theorie und Praxis der Programmiersprache jedoch nicht besonders dominieren. Es gibt verschiedene Gründe dafür, aber der vielleicht wichtigste ist, dass TMs oder Programme, die auf TMs laufen (anders als z. B. Lambda-Kalküle oder Prozess-Kalküle), nicht algebraisch aufgebaut sind. Dies macht es schwierig, Typentheorien zu entwickeln, die die Hauptstütze der Programmiersprachtheorie waren.

Eines der schönen Dinge an Turing-Maschinen ist, dass sie auf Strings anstatt auf natürlichen Zahlen oder Lambda-Termen arbeiten, weil die Eingabe und Ausgabe vieler Probleme auf natürliche Weise als Strings formuliert werden können. Ich weiß jedoch nicht, ob dies ein „historischer“ Grund ist oder nicht.

Neben der Tatsache, dass Turing-Maschinen ein überzeugendes Modell der Stift-Papier-Berechnung sind (der „intuitive Begriff der Berechnung“), denke ich, dass sie eine Reihe von Merkmalen besitzen, die häufig nützlich sind, insbesondere wenn Theoreme über sie bewiesen werden:

• Sie sind formal leicht zu beschreiben und haben eine einfache operative Semantik.
• es ist einfach, ihre zeitliche und räumliche Komplexität konkret zu definieren;
• Realistischere (und komplexere) Modelle elektronischer Computer, z. B. Maschinen mit wahlfreiem Zugriff, können von TMs mit einem polynomiellen Overhead simuliert werden und umgekehrt.

Es war das erste, das Wirkung gezeigt hat, und hat sich daher insbesondere in der Komplexitätstheorie bewährt. Das ist ein schwacher Grund, aber die Leute arbeiten so. Wir arbeiten zuerst an alten offenen Problemen, anstatt neue zu deklarieren.