Turings Beweis - Turing's proof

Turings Beweis ist ein Beweis von Alan Turing , der erstmals im Januar 1937 unter dem Titel „ On Computable Numbers, with an Application to the Entscheidungsproblem “ veröffentlicht wurde. Es war der zweite Beweis (nach dem Theorem von Church ) für die Vermutung, dass einige rein mathematische Ja-Nein-Fragen niemals rechnerisch beantwortet werden können; technisch gesehen sind einige Entscheidungsprobleme " unentscheidbar " in dem Sinne, dass es keinen einzelnen Algorithmus gibt, der unfehlbar auf jede Instanz des Problems eine richtige "Ja" oder "Nein"-Antwort gibt. In Turings eigenen Worten: "...was ich beweisen werde, unterscheidet sich ziemlich von den bekannten Ergebnissen von Gödel ... Ich werde nun zeigen, dass es keine allgemeine Methode gibt, die sagt, ob eine gegebene Formel U in K beweisbar ist [ Principia Mathematica ]..." ( Undecidable , S. 145).

Turing folgte diesem Beweis mit zwei anderen. Die zweite und dritte stützen sich beide auf die erste. Alle stützen sich auf seine Entwicklung von schreibmaschinenähnlichen "Rechenmaschinen", die einem einfachen Regelwerk gehorchen, und seine anschließende Entwicklung einer "Universal-Rechenmaschine".

Zusammenfassung der Beweise

In seinem Beweis, dass das Entscheidungsproblem keine Lösung haben kann, ging Turing von zwei Beweisen aus, die zu seinem endgültigen Beweis führen sollten. Sein erster Satz ist am relevantesten für das Halteproblem , der zweite ist für den Satz von Rice relevanter .

Erster Beweis : dass es keine "Rechenmaschine" gibt, die entscheiden kann, ob eine beliebige "Rechenmaschine" (dargestellt durch eine ganze Zahl 1, 2, 3, . . .) Zahl in binär ad infinitum): "...wir haben kein allgemeines Verfahren, um dies in endlich vielen Schritten zu tun" (S. 132, ebd .). Turings Beweis zeigt, obwohl er den "diagonalen Prozess" zu verwenden scheint, tatsächlich, dass seine Maschine (genannt H) nicht ihre eigene Zahl berechnen kann, geschweige denn die gesamte diagonale Zahl ( Cantors diagonales Argument ): die Annahme, dass B [die Diagonalzahl] berechenbar ist“ ( Undecidable , S. 132). Der Beweis erfordert nicht viel Mathematik.

Zweiter Beweis : Dieser ist den Lesern vielleicht bekannter als der Satz von Rice : "Wir können weiter zeigen, dass es keine Maschine E geben kann, die, wenn sie mit dem SD ["Programm"] einer beliebigen Maschine M geliefert wird, bestimmt, ob M jemals druckt ein gegebenes Symbol (0 sagen) " (seine Kursivschrift, Undecidable , S. 134).

Dritter Beweis : "Entsprechend jeder Rechenmaschine M konstruieren wir eine Formel Un(M) und wir zeigen, dass es, wenn es eine allgemeine Methode gibt, um zu bestimmen, ob Un(M) beweisbar ist, eine allgemeine Methode gibt, um zu bestimmen, ob M jemals druckt 0" ( Unentscheidbar , S. 145).

Der dritte Beweis erfordert die Verwendung formaler Logik, um ein erstes Lemma zu beweisen, gefolgt von einem kurzen Wortbeweis des zweiten:

Lemma 1: Wenn S1 [Symbol "0"] in einer vollständigen Konfiguration von M auf dem Band erscheint, dann ist Un(M) beweisbar. ( Unentscheidbar , S. 147)
Lemma 2: [Die Umkehrung] Wenn Un(M) beweisbar ist, erscheint S1 [Symbol "0"] in einer vollständigen Konfiguration von M auf dem Band. ( Unentscheidbar , S. 148)

Schließlich beweist Turing in nur 64 Wörtern und Symbolen per reductio ad absurdum, dass "das Hilbert-Entscheidungsproblem keine Lösung haben kann" ( Undecidable , S. 145).

Zusammenfassung des ersten Beweises

Turing schuf ein Dickicht von Abkürzungen. Definitionen finden Sie im Glossar am Ende des Artikels.

Einige wichtige Klarstellungen:

Turings Maschine H versucht, eine diagonale Zahl von Nullen und Einsen zu drucken.
Diese diagonale Zahl wird erzeugt, wenn H tatsächlich jede "erfolgreiche" Maschine in der Auswertung "simuliert" und die R-te "Zahl" (1 oder 0) der R-ten "erfolgreichen" Maschine druckt.

Turing verbrachte einen Großteil seiner Arbeit damit, seine Maschinen zu "konstruieren", um uns von ihrer Wahrheit zu überzeugen. Dies war durch seine Verwendung der Beweisform reductio ad absurdum erforderlich . Wir müssen den "konstruktiven" Charakter dieses Beweises betonen. Turing beschreibt, was eine echte Maschine sein könnte, wirklich baubar. Das einzig fragwürdige Element ist die Existenz der Maschine D, die dieser Beweis schließlich als unmöglich erweisen wird.

Turing beginnt den Beweis mit der Behauptung der Existenz einer „Entscheidungs-/Bestimmungsmaschine“ D. Wenn ein SD (Zeichenkette A, C, D, L, R, N, Semikolon „;“) gefüttert wird, wird es feststellen, ob dies SD (Symbolstring) steht für eine „Rechenmaschine“, die entweder „rund“ – und damit „unbefriedigend u“ – oder „kreisfrei“ – und damit „befriedigend s“ ist.

Turing hat zuvor in seinem Kommentar gezeigt, dass alle "Computermaschinen - Maschinen, die eine Zahl als 1 und 0 für immer berechnen - als SD auf das Band der "universellen Maschine" U geschrieben werden können Der Beweis wird damit verbracht, zu zeigen, dass eine universelle Maschine wirklich existiert, d
Es gibt wirklich eine universelle Maschine U
Für jede Zahl N existiert wirklich ein eindeutiges SD,
Jede Turingmaschine hat eine SD
Jede SD auf dem Band von U kann von U „ausgeführt“ werden und erzeugt die gleiche „Ausgabe“ (Abbildungen 1, 0) wie das Originalgerät.

Turing macht keinen Kommentar dazu, wie Maschine D ihre Arbeit verrichtet. Aus Gründen der Argumentation nehmen wir an, dass D zuerst prüfen würde, ob die Zeichenkette "wohlgeformt" ist (dh in Form eines Algorithmus und nicht nur einer Verwürfelung von Symbolen), und wenn nicht, dann verwerfen würde. Dann würde es „Kreisjagd“ gehen. Dazu würde es vielleicht „Heuristiken“ (Tricks: gelehrt oder gelernt) verwenden. Für Beweiszwecke sind diese Angaben nicht von Bedeutung.

Turing beschreibt dann (eher locker) den Algorithmus (die Methode), dem eine Maschine folgen soll, die er H nennt. Maschine H enthält in sich die Entscheidungsmaschine D (also ist D eine „Unterroutine“ von H). Der Algorithmus von Maschine H wird in der Befehlstabelle von H oder vielleicht in der Standardbeschreibung von H auf Band ausgedrückt und mit der universellen Maschine U vereinigt; Turing gibt dies nicht an.

Im Zuge der Beschreibung der universellen Maschine U hat Turing gezeigt, dass die SD (Buchstabenfolge ähnlich einem „Programm“) einer Maschine in eine ganze Zahl (Basis 8) umgewandelt werden kann und umgekehrt. Jede Zahl N (in Basis 8) kann mit den folgenden Ersetzungen in ein SD umgewandelt werden: 1 durch A, 2 durch C, 3 durch D, 4 durch L, 5 durch R, 6 durch N, 7 durch Semikolon ";".

Wie sich herausstellt, ist die eindeutige Nummer (DN) von Maschine H die Nummer "K". Wir können daraus schließen, dass K eine sehr lange Zahl ist, die vielleicht Zehntausende von Stellen lang ist. Aber das ist für das Folgende nicht wichtig.

Maschine H ist dafür verantwortlich, eine beliebige Zahl N in eine äquivalente SD-Symbolkette zu konvertieren, damit die Untermaschine D testen kann. (In der Programmiersprache: H übergibt ein beliebiges "SD" an D, und D gibt "befriedigend" oder "unbefriedigend" zurück.) Maschine H ist auch dafür verantwortlich, eine Zählung R ("Rekord"?) erfolgreicher Zahlen zu führen (wir nehmen an, dass die Anzahl der „erfolgreichen“ SDs, dh R, ist viel geringer als die Anzahl der getesteten SDs, dh N. Schließlich druckt H auf einen Abschnitt seines Bandes eine diagonale Zahl „beta-primed“ B'. H erzeugt dieses B' durch „Simulieren“ (im Computersinn) der „Bewegungen“ jeder „zufriedenstellenden“ Maschine/Zahl; schließlich wird diese Maschine/Zahl im Test zu ihrer R-ten „Zahl“ (1 oder 0) und H H ist dann dafür verantwortlich, das von der Simulation hinterlassene Chaos zu beseitigen, N zu erhöhen und mit seinen Tests fortzufahren , bis ins Unendliche .

Hinweis: Alle diese Maschinen, nach denen H sucht, sind das, was Turing "Computermaschinen" nannte. Diese berechnen Binär-Dezimal-Zahlen in einem endlosen Strom von dem, was Turing "Zahlen" nannte: nur die Symbole 1 und 0.

Ein Beispiel zur Veranschaulichung des ersten Beweises

Ein Beispiel: Angenommen, Maschine H hat 13472 Zahlen getestet und 5 zufriedenstellende Zahlen erzeugt, dh H hat die Zahlen 1 bis 13472 in SDs (Symbolketten) umgewandelt und sie zum Test an D übergeben. Als Konsequenz hat H 5 zufriedenstellende Zahlen ausgezählt und die erste bis zur 1. "Zahl", die zweite zur 2. Zahl, die dritte zur 3. Zahl, die vierte zur 4. Zahl und die fünfte zur 5. Zahl laufen lassen. Die Zählung steht jetzt bei N = 13472, R = 5 und B' = ".10011" (zum Beispiel). H räumt das Durcheinander auf seinem Band auf und fährt fort:

H inkrementiert N = 13473 und wandelt "13473" in die Symbolkette ADRLD um. Wenn die Untermaschine D ADLRD als nicht zufriedenstellend erachtet, dann belässt H den Zähldatensatz R bei 5. H erhöht die Zahl N auf 13474 und geht weiter. Auf der anderen Seite, wenn D ADRLD für zufriedenstellend hält, dann wird H R auf 6 erhöhen. H wird N (wieder) in ADLRD umwandeln [dies ist nur ein Beispiel, ADLRD ist wahrscheinlich nutzlos] und es mit der Universalmaschine U „ausführen“ bis diese zu testende Maschine (U "läuft" ADRLD) druckt ihre 6. „Ziffer“, dh 1 oder 0. H druckt diese 6. Zahl (zB „0“) im „Ausgabe“-Bereich seines Bandes (zB B' = „.100110“).

H räumt das Chaos auf und erhöht dann die Zahl N auf 13474.

Der ganze Vorgang entwirrt sich, wenn H bei seiner eigenen Zahl K ankommt. Wir fahren mit unserem Beispiel fort. Angenommen, der Erfolgszähler/Rekord R steht bei 12. H kommt schließlich zu seiner eigenen Zahl minus 1, dh N = K-1 = 4335...321 4 , und diese Zahl ist nicht erfolgreich. Dann erhöht H N um K = 4355...321 5 , dh seine eigene Zahl zu erzeugen . H wandelt diese in „LDDR ... DCAR“ und übergibt sie an den Entscheidungs Maschine D. Entscheidungsmaschine D zurückkehren muss „befriedigend“ (das heißt: H muss per Definition weitermachen und auf die Prüfung, ad infinitum , weil es " kreisfrei"). H inkrementiert nun die Zählung R von 12 auf 13 und wandelt dann die getestete Zahl K wieder in ihre SD um und verwendet U, um sie zu simulieren. Aber das bedeutet, dass H seine eigenen Bewegungen simuliert. Was wird die Simulation als erstes tun? Diese Simulation K-aka-H erzeugt entweder ein neues N oder „setzt“ das „alte“ N auf 1. Dieses „K-aka-H“ erzeugt entweder ein neues R oder „setzt“ das „alte“ R auf 0 zurück. Alt -H "läuft" neues "K-aka-H", bis es seine 12. Zahl erreicht.

Aber es schafft es nie auf die 13. Stelle; K-aka-H kommt schließlich wieder bei 4355...321 5 an und K-aka-H muss den Test wiederholen. K-aka-H wird nie die 13. Zahl erreichen. Die H-Maschine druckt wahrscheinlich nur Kopien von sich selbst bis ins Unendliche über ein leeres Band. Dies widerspricht jedoch der Prämisse, dass H eine zufriedenstellende, nicht kreisförmige Rechenmaschine ist, die ewig die Einsen und Nullen der Diagonalzahlen druckt. (Wir werden dasselbe sehen, wenn N auf 1 zurückgesetzt wird und R auf 0 zurückgesetzt wird.)

Wenn der Leser dies nicht glaubt, kann er einen "Stub" für die Entscheidungsmaschine D schreiben (Stub "D" liefert "befriedigend") und dann selbst sehen, was passiert, wenn Maschine H auf ihre eigene Nummer trifft.

Zusammenfassung des zweiten Beweises

Weniger als eine Seite lang ist der Übergang von den Prämissen zum Schluss undeutlich.

Turing geht durch reductio ad absurdum vor . Er behauptet die Existenz einer Maschine E, die, wenn sie die SD (Standardbeschreibung, dh "Programm") einer beliebigen Maschine M erhält, bestimmt, ob M jemals ein gegebenes Symbol druckt (sagen wir). Er behauptet nicht, dass dieses M eine "Computermaschine" ist.

Angesichts der Existenz der Maschine E geht Turing wie folgt vor:

  1. Wenn Maschine E existiert, dann existiert eine Maschine G, die bestimmt, ob M unendlich oft 0 druckt, UND
  2. Wenn E existiert, dann existiert ein anderer Prozess [wir können den Prozess/die Maschine G' als Referenz nennen] der bestimmt, ob M unendlich oft 1 ausgibt, DESHALB
  3. Wenn wir G mit G' kombinieren, haben wir einen Prozess, der bestimmt, ob M unendlich viele Zahlen ausgibt, UND
  4. WENN der Prozess "G mit G'" bestimmt, dass M unendlich viele Ziffern druckt, DANN hat "G mit G'" bestimmt, dass M kreisfrei ist, ABER
  5. Dieser Prozess "G mit G'", der nach Beweis 1 bestimmt, ob M kreisfrei ist, kann nicht existieren, DAHER
  6. Maschine E existiert nicht.

Details zum zweiten Beweis

Die Schwierigkeit beim Beweis ist Schritt 1. Dem Leser wird dadurch geholfen, dass er erkennt, dass Turing sein subtiles Handwerk nicht erklärt. (Kurz gesagt: Er verwendet bestimmte Äquivalenzen zwischen den „Existenz-“ und „Universal-Operatoren“ zusammen mit ihren entsprechenden Ausdrücken, die mit logischen Operatoren geschrieben sind.)

Hier ein Beispiel: Angenommen, wir sehen vor uns einen Parkplatz voller Hunderter von Autos. Wir beschließen, das ganze Los zu durchsuchen und suchen nach: „Autos mit platten (schlechten) Reifen“. Nach etwa einer Stunde haben wir zwei „Autos mit schlechten Reifen“ gefunden. Wir können jetzt mit Sicherheit sagen: „Manche Autos haben schlechte Reifen“. Oder wir könnten sagen: „Es stimmt nicht, dass alle Autos gute Reifen haben“. Oder: „Es stimmt: ‚Nicht alle Autos haben gute Reifen“. Kommen wir zu einem anderen Los. Hier entdecken wir: „Alle Autos haben gute Reifen“. Wir könnten sagen: „Es gibt keinen einzigen Fall, in dem ein Auto einen schlechten Reifen hat.“ Wir sehen also, dass wir, wenn wir etwas über jedes Auto einzeln sagen können, etwas über ALLE zusammen sagen können.

Das macht Turing: Aus M erstellt er eine Sammlung von Maschinen { M 1, M 2, M 3, M 4, ..., Mn } und schreibt über jede einen Satz: „ X druckt mindestens eine 0“ und erlaubt nur zwei „ Wahrheitswerte “, True = leer oder False = :0:. Einer nach dem anderen bestimmt er den Wahrheitswert des Satzes für jede Maschine und erstellt eine Folge von Leerzeichen oder :0: oder eine Kombination davon. Wir könnten so etwas erhalten: „ M 1 druckt eine 0“ = wahr UND „ M 2 druckt eine 0“ = wahr UND „ M 3 druckt eine 0“ = wahr UND „ M 4 druckt eine 0“ = falsch, ... UND „ Mn druckt eine 0“ = Falsch. Er bekommt die Schnur

BBB:0::0::0: ... :0: ... bis ins Unendliche

wenn es unendlich viele Maschinen gibt Mn . Wenn andererseits jede Maschine ein "Wahr" produziert hätte, dann wäre der Ausdruck auf dem Band

BBBBB....BBBB ... bis ins Unendliche

So hat Turing Aussagen über jede einzeln betrachtete Maschine in eine einzelne "Aussage" (String) über alle umgewandelt. Angesichts der Maschine (er nennt sie G), die diesen Ausdruck erzeugt hat, kann er sie mit seiner Maschine E testen und feststellen, ob sie jemals eine 0 produziert. In unserem ersten Beispiel oben sehen wir, dass dies tatsächlich der Fall ist, also wissen wir, dass nicht alle Ms in unserer Sequenz drucken 0s. Das zweite Beispiel zeigt jedoch, dass jedes Mn in unserer Folge eine 0 erzeugt hat, da die Zeichenfolge leer ist.

Turing muss nur noch einen Prozess erstellen, um die Sequenz von Mns aus einem einzelnen M zu erstellen.

Angenommen, M druckt dieses Muster:

M => ...AB01AB0010AB…

Turing erstellt eine weitere Maschine F, die M nimmt und eine Sequenz von Mns herausrechnet, die nacheinander die ersten n 0 in „0-bar“ ( 0 ) umwandeln :

Er stellt fest, ohne Details zu zeigen, dass diese Maschine F wirklich baufähig ist. Wir können sehen, dass eines von ein paar Dingen passieren könnte. F hat möglicherweise keine Maschinen mehr, die Nullen haben, oder es muss endlos Maschinen erstellen, um „die Nullen zu löschen“.

Turing kombiniert nun die Maschinen E und F zu einer zusammengesetzten Maschine G. G beginnt mit dem ursprünglichen M und verwendet dann F, um alle Nachfolgemaschinen M1, M2, zu erzeugen. . ., Mn. Dann verwendet G E, um jede Maschine zu testen, die mit M beginnt. Wenn E feststellt, dass eine Maschine nie eine Null druckt, druckt G :0: für diese Maschine. Wenn E erkennt, dass eine Maschine eine 0 ausgibt (wir nehmen an, Turing sagt es nicht), dann druckt G :: oder überspringt einfach diese Eingabe und lässt die Felder leer. Wir können sehen, dass ein paar Dinge passieren können.

G druckt keine Nullen, immer, wenn alle Mn Nullen drucken, ODER,
G wird unendlich Nullen drucken, wenn alle M keine Nullen drucken, ODER,
G wird für eine Weile Nullen drucken und dann aufhören.

Was passiert nun, wenn wir E auf G selbst anwenden?

Wenn E(G) bestimmt, dass G niemals eine 0 ausgibt, dann wissen wir, dass alle Mn Nullen gedruckt haben. Und das bedeutet, dass M selbst Nullen ad infinitum druckt, weil alle Mn von M stammen, ODER
Wenn E(G) feststellt, dass G eine 0 ausgibt, dann wissen wir, dass nicht alle Mn Nullen drucken; daher druckt M keine Nullen ad infinitum .

Da wir den gleichen Prozess anwenden können, um zu bestimmen, ob M unendlich oft 1 druckt. Wenn wir diese Prozesse kombinieren, können wir feststellen, dass M unendlich viele Einsen und Nullen druckt oder nicht . Damit haben wir eine Methode zur Bestimmung, ob M kreisfrei ist. Nach Beweis 1 ist dies unmöglich. Die erste Behauptung, dass E existiert, ist also falsch: E existiert nicht.

Zusammenfassung des dritten Beweises

Hier beweist Turing, "dass das Hilbert- Entscheidungsproblem keine Lösung haben kann" ( Undecidable , S. 145). Hier ist er

…zeigen, dass es kein allgemeines Verfahren geben kann, um zu bestimmen, ob eine gegebene Formel U des Funktionalkalküls K beweisbar ist. ( ebenda .)

Beide Lemmas #1 und #2 sind erforderlich, um das notwendige "IF AND ONLY IF" (dh logische Äquivalenz ) zu bilden, das der Beweis erfordert:

Eine Menge E ist genau dann berechenbar entscheidbar, wenn sowohl E als auch ihr Komplement berechenbar aufzählbar sind (Franzén, S. 67)

Turing demonstriert die Existenz einer Formel Un (M), die praktisch besagt, dass „in einer vollständigen Konfiguration von M 0 auf dem Band erscheint“ (S. 146). Diese Formel ist WAHR, das heißt, sie ist "konstruierbar", und er zeigt, wie das geht.

Dann beweist Turing zwei Lemmas, von denen das erste die ganze harte Arbeit erfordert. (Die zweite ist die Umkehrung der ersten.) Dann verwendet er die reductio ad absurdum , um sein Endergebnis zu beweisen:

  1. Es existiert eine Formel Un (M). Diese Formel ist WAHR, UND
  2. Wenn das Entscheidungsproblem gelöst werden kann, DANN existiert ein mechanischer Prozess zur Bestimmung, ob Un (M) beweisbar (ableitbar) ist, UND
  3. Nach Lemmas 1 und 2: Un (M) ist beweisbar, WENN UND NUR WENN 0 in einer "vollständigen Konfiguration" von M vorkommt, UND
  4. WENN 0 in einer "vollständigen Konfiguration" von M vorkommt, DANN existiert ein mechanischer Prozess, der bestimmt, ob ein beliebiges M jemals 0 druckt , UND
  5. Nach Beweis 2 existiert kein mechanischer Prozess, der bestimmt, ob ein beliebiges M jemals 0 druckt , DAHER
  6. Un (M) ist nicht beweisbar (es ist WAHR, aber nicht beweisbar ), was bedeutet, dass das Entscheidungsproblem unlösbar ist.

Details zum dritten Beweis

[Wenn die Leser beabsichtigen, den Korrekturabzug im Detail zu studieren, sollten sie ihre Kopien der Seiten des dritten Korrekturabzuges mit den von Turing gelieferten Korrekturen korrigieren. Der Leser sollte auch über einen soliden Hintergrund in (i) Logik (ii) dem Artikel von Kurt Gödel : " On Formally Undecidable Propositions of Principia Mathematica and Related Systems " (nachgedruckt in Undecidable , S. 5) verfügen . Um Hilfe bei Gödels Aufsatz zu erhalten, sollten sie zB Ernest Nagel und James R. Newman konsultieren , Gödel's Proof , New York University Press, 1958.]

Um den technischen Details folgen zu können, muss der Leser die Definition von „beweisbar“ verstehen und wichtige „Hinweise“ kennen.

„Beweisbar“ bedeutet im Sinne von Gödel, dass (i) das Axiomensystem selbst mächtig genug ist, um den Satz „Dieser Satz ist beweisbar“ zu produzieren (auszudrücken) und (ii) dass in jedem beliebigen „wohlgeformten“ Beweis die Symbole führen durch Axiome, Definitionen und Substitution zu den Symbolen der Konklusion.

Erster Hinweis: "Setzen wir die Beschreibung von M in die erste Standardform von §6". Abschnitt 6 beschreibt die sehr spezifische "Kodierung" der Maschine M auf dem Band einer "universellen Maschine" U. Dies erfordert, dass der Leser einige Eigenheiten der universellen Maschine U von Turing und des Kodierungsschemas kennt.

(i) Die universelle Maschine ist ein Satz von "universellen" Befehlen, die sich in einer "Befehlstabelle" befinden. Getrennt davon befindet sich auf dem Band von U eine "Computermaschine" M als "M-Code". Die universelle Instruktionstabelle kann die Symbole A, C, D, 0, 1, u, v, w, x, y, z, : auf das Band drucken . Die verschiedenen Maschinen M können diese Symbole nur indirekt drucken, indem sie U befehlen, sie zu drucken.

(ii) Der "Maschinencode" von M besteht nur aus wenigen Buchstaben und dem Semikolon, dh D, C, A, R, L, N, ; . Nirgendwo innerhalb des "Codes" von M werden die numerischen "Zahlen" (Symbole) 1 und 0 jemals erscheinen. Wenn M möchte, dass U ein Symbol aus dem Sammlungsleerzeichen 0, 1 ausgibt, verwendet es einen der folgenden Codes, um U anzuweisen, sie zu drucken. Um die Sache noch verwirrender zu machen, nennt Turing diese Symbole S0, S1 und S2, dh

leer = S0 = D
0 = S1 = DC
1 = S2 = DCC

(iii) Eine "Computermaschine", ob sie direkt in eine Tabelle eingebaut ist (wie seine ersten Beispiele zeigen), oder als Maschinencode M auf dem Band der Universalmaschine U druckt ihre Nummer auf ein leeres Band (rechts von M -Code, falls vorhanden) als 1 s und 0 s immer weiter nach rechts.

(iv) Wenn eine "Computermaschine" U+"M-Code" ist, dann erscheint "M-Code" zuerst auf dem Band; das Band hat ein linkes Ende und der "M-Code" beginnt dort und verläuft auf abwechselnden Feldern nach rechts. Wenn der M-Code zu Ende geht (und das muss er, weil angenommen wird, dass diese M-Codes endliche Algorithmen sind), beginnen die "Zahlen" als 1 s und 0 s auf abwechselnden Quadraten und schreiten für immer nach rechts fort. Turing verwendet die (leeren) alternativen Quadrate (genannt "E"-"löschbare"-Quadrate), um U+"M-Code" zu helfen, den Überblick zu behalten, wo die Berechnungen sind, sowohl im M-Code als auch in den "Figuren", die der Maschine druckt.

(v) Eine "vollständige Konfiguration" ist ein Drucken aller Symbole auf dem Band, einschließlich M-Code und "Figuren" bis zu diesem Punkt, zusammen mit der gerade gescannten Figur (mit einem Zeigerzeichen links neben dem gescanntes Symbol?). Wenn wir Turings Bedeutung richtig interpretiert haben, wird dies eine sehr lange Reihe von Symbolen sein. Ob jedoch der gesamte M-Code wiederholt werden muss, ist unklar; es ist nur ein Ausdruck des aktuellen M-Code-Befehls sowie der Ausdruck aller Ziffern mit einem Ziffernmarker erforderlich).

(vi) Turing reduzierte die riesige mögliche Anzahl von Befehlen in "M-Code" (wieder: der Code von M, der auf dem Band erscheinen soll) auf eine kleine kanonische Menge, eine von dreien ähnlich dieser: {qi Sj Sk R ql} Beispiel: Wenn die Maschine die Anweisung #qi ausführt und das Symbol Sj auf dem gescannten Feld ist, dann Drucken Sie das Symbol Sk und gehen Sie nach rechts und gehen Sie dann zur Anweisung ql : Die anderen Anweisungen sind ähnlich, Codierung für "Links" L und "Keine Bewegung" N Diese Menge wird durch die Zeichenkette qi = DA...A, Sj = DC...C, Sk = DC...C, R, ql = DA....A codiert. Jede Anweisung wird durch das Semikolon von einer anderen getrennt. Zum Beispiel bedeutet {q5, S1 S0 L q3}: Anweisung #5: Wenn das gescannte Symbol 0 ist, dann leer drucken , nach links gehen und dann zu Anweisung #3 gehen. Es ist wie folgt codiert

; DAAAAADCDLDAAA

Zweiter Hinweis: Turing verwendet Ideen, die in Gödels Aufsatz eingeführt wurden, dh die "Gödelisierung" (zumindest eines Teils) der Formel für Un (M). Dieser Hinweis erscheint nur als Fußnote auf Seite 138 ( Undecidable ): "Eine Folge von r Primzahlen wird bezeichnet durch ^ (r)" ( ebd .) [Hier wird r in Klammern "erhöht".] Diese "Reihenfolge von Primzahlen" erscheint in einer Formel namens F^(n).

Dritter Hinweis: Dies verstärkt den zweiten Hinweis. Turings ursprünglicher Beweisversuch verwendet den Ausdruck:

(Eu)N(u) & (x)(... etc. ...) ( Unentscheidbar , S. 146)

Früher in der Arbeit hatte Turing diesen Ausdruck zuvor verwendet (S. 138) und definierte N(u) als "u ist eine nicht-negative ganze Zahl" ( ebd .) (dh eine Gödel-Zahl). Aber mit den Bernays-Korrekturen hat Turing diesen Ansatz (dh die Verwendung von N(u)) aufgegeben und die einzige Stelle, an der "die Gödel-Zahl" explizit erscheint, ist dort, wo er F^(n) verwendet.

Was bedeutet das für den Beweis? Der erste Hinweis bedeutet, dass eine einfache Untersuchung des M-Codes auf dem Band nicht erkennen lässt, ob jemals ein Symbol 0 von U+"M-Code" gedruckt wird. Eine Testmaschine könnte nach dem Auftreten von DC in einer der Zeichenketten suchen , die eine Anweisung darstellen. Aber wird diese Anweisung jemals "ausgeführt"? Etwas muss "den Code ausführen", um das herauszufinden. Dieses Etwas kann eine Maschine sein oder Zeilen in einem formalen Beweis, zB Lemma #1.

Der zweite und dritte Hinweis bedeuten, dass der Beweis schwierig ist, da Gödels Arbeit als Grundlage dient.

Im folgenden Beispiel werden wir tatsächlich ein einfaches "Theorem" konstruieren - ein kleines Post-Turing-Maschinenprogramm "run it". Wir werden sehen, wie mechanisch ein richtig entworfener Satz sein kann. Ein Beweis, wie wir sehen werden, ist genau das, ein "Test" des Theorems, den wir machen, indem wir ein "Beweisbeispiel" am Anfang einfügen und sehen, was am Ende herauskommt.

Beide Lemmas #1 und #2 werden benötigt, um das notwendige "IF AND ONLY IF" (dh logische Äquivalenz) zu bilden, das der Beweis erfordert:

Eine Menge E ist genau dann berechenbar entscheidbar, wenn sowohl E als auch ihr Komplement berechenbar aufzählbar sind. (Franzén, S. 67)

Um Franzén zu zitieren:

Ein Satz A heißt in einem formalen System S entscheidbar, wenn entweder A oder seine Negation in S beweisbar ist. (Franzén, S. 65)

Franzén hat früher in seinem Buch "beweisbar" definiert:

Ein formales System ist ein System von Axiomen (ausgedrückt in einer formal definierten Sprache) und Argumentationsregeln (auch Inferenzregeln genannt), die verwendet werden, um die Theoreme des Systems abzuleiten . Ein Theorem ist jede Aussage in der Sprache des Systems, die durch eine Reihe von Anwendungen der Argumentationsregeln, ausgehend von den Axiomen, erhältlich ist. Ein Beweis ist eine endliche Folge solcher Anwendungen, die zu einem Satz als Konklusion führt. ( ebd. S. 17)

Somit ist ein "Satz" eine Zeichenkette und ein Satz ist eine Zeichenkette von Symbolen.

Turing steht vor folgender Aufgabe:

ein universelles Turing-Maschinen- "Programm" und die numerischen Symbole auf dem Band (Turings "Figuren", Symbole "1" und "0") in ein "Theorem" umzuwandeln – d. h. eine (ungeheuer lange) Folge von Sätzen die die aufeinanderfolgenden Aktionen der Maschine, (alle) die Figuren des Bandes und die Position des "Bandkopfes" definieren.

Somit wird die "Satzfolge" eine Kette von Symbolketten sein. Die einzigen erlaubten Einzelsymbole stammen von Gödels Symbolen, die in seiner Arbeit definiert sind. (Im folgenden Beispiel verwenden wir die "<" und ">" um eine "Figur", um anzuzeigen, dass die "Figur" das Symbol ist, das von der Maschine gescannt wird ).

Ein Beispiel zur Veranschaulichung des dritten Beweises

Im Folgenden müssen wir uns daran erinnern, dass jede von Turings „Computermaschinen“ ein Binärzahlengenerator/Schöpfer ist, der mit der Arbeit auf „blankem Band“ beginnt. Richtig konstruiert dreht es sich immer bis ins Unendliche, aber seine Anweisungen sind immer endlich. In Turings Beweisen hatte Turings Band ein „linkes Ende“, verlängerte sich jedoch nach rechts bis ins Unendliche. Als Beispiel nehmen wir im Folgenden an, dass die „Maschine“ keine Universalmaschine ist, sondern die einfachere „dedizierte Maschine“ mit den Anweisungen in der Tabelle.

Unser Beispiel basiert auf einem modifizierten Post-Turing-Maschinenmodell einer Turingmaschine. Dieses Modell druckt nur die Symbole 0 und 1. Das leere Band wird als alle b angesehen. Unser modifiziertes Modell erfordert, dass wir den 7 Post-Turing-Anweisungen zwei weitere Anweisungen hinzufügen. Die von uns verwendeten Abkürzungen sind:

R, RIGHT: nach rechts schauen und Band nach links bewegen oder Bandkopf nach rechts bewegen
L, LEFT : nach links schauen und Band nach rechts bewegen oder Bandkopf nach links bewegen
E, gescanntes Quadrat LÖSCHEN (zB Quadrat leer machen)
P0 ,: PRINT 0 im gescannten Quadrat
P1,: PRINT 1 im gescannten Quadrat
Jb_n, JUMP-IF-leer-zu-Anweisung_#n,
J0_n, JUMP-IF-0-zu-Anweisung_#n,
J1_n, JUMP-IF-1 -to-instruction_#n,
HALT.

In den Fällen R, L, E, P0 und P1 geht die Maschine nach Erledigung ihrer Aufgabe zur nächsten Anweisung in numerischer Folge über; dito für die Sprünge, wenn ihre Tests fehlschlagen.

Aber der Kürze halber verwenden unsere Beispiele nur drei Quadrate. Und diese werden immer als Leerzeichen mit dem gescannten Quadrat links beginnen: zB bbb. Mit zwei Symbolen 1, 0 und leer können wir 27 verschiedene Konfigurationen haben:

bbb, bb0, bb1, b0b, b00, b01, b1b, b10, b11, 0bb, 0b0, 0b1, 00b, 000, 001, 01b, 010, 011, 1bb, 1b0, 1b1, 10b, 100, 101, 11b, 110, 111

Wir müssen hier vorsichtig sein, denn es ist durchaus möglich, dass ein Algorithmus (vorübergehend) Leerzeichen zwischen den Zahlen lässt, dann zurückkommt und etwas ausfüllt. Wahrscheinlicher ist, dass ein Algorithmus dies absichtlich tut. Tatsächlich macht die Turing-Maschine dies – sie druckt auf abwechselnden Feldern und lässt Leerzeichen zwischen den Zahlen, damit sie Locator-Symbole drucken kann.

Turing ließ immer alternative Quadrate leer, damit seine Maschine ein Symbol links von einer Zahl platzieren konnte (oder einem Buchstaben, wenn die Maschine die Universalmaschine ist und das gescannte Quadrat tatsächlich im „Programm“ ist). In unserem kleinen Beispiel verzichten wir darauf und legen einfach Symbole ( ) um das gescannte Symbol herum, wie folgt:

b(b)0 das bedeutet, "Band ist Leerzeichen-links vom linken Leerzeichen, aber das linke Leerzeichen ist 'im Spiel', das gescannte-Quadrat-ist-Leerzeichen, '0', Leerzeichen-nach-rechts"
1 (0)1 bedeutet, "Band ist Leerzeichen-nach-links, dann 1, gescanntes Quadrat ist '0'"

Schreiben wir ein einfaches Programm:

Start: P1, R, P1, R, P1, H

Denken Sie daran, dass wir immer mit einem leeren Band beginnen. Die vollständige Konfiguration druckt die Symbole auf das Band, gefolgt von der nächsten Anweisung:

start config: (b) P1,
config #1: (1) R,
config #2: 1(b) P1,
config #3: 1(1) R,
config #4: 11(b) P1,
config #5 : 11(1) H

Fügen wir „Sprung“ in die Formel ein. Dabei entdecken wir, warum die komplette Konfiguration die Bandsymbole enthalten muss. (Eigentlich sehen wir dies unten besser.) Dieses kleine Programm druckt drei "1"en nach rechts, kehrt die Richtung um und bewegt sich nach links und druckt Nullen, bis es auf eine Leerstelle trifft. Wir drucken alle Symbole, die unsere Maschine verwendet:

Start: P1, R, P1, R, P1, P0, L, J1_7, H
(b)bb P1,
(1)bb R,
1(b)b P1,
1(1)b R,
11(b) P1 ,
11(1) P0,
11(0) L,
1(1)0 J1_7
1(1)0 L
(1)10 J0_7
(1)10 L
(b)110 J0_7
(b)110 H

Hier am Ende stellen wir fest, dass links ein Leerzeichen „ins Spiel gekommen“ ist, also belassen wir es als Teil der Gesamtkonfiguration.

Da wir unsere Arbeit richtig gemacht haben, fügen wir die Startbedingungen hinzu und sehen, „wo der Satz hingeht“. Die resultierende Konfiguration – die Zahl 110 – ist der BEWEIS.

  • Turings erste Aufgabe bestand darin, einen verallgemeinerten Ausdruck mit logischen Symbolen zu schreiben, um genau auszudrücken, was sein Un(M) tun würde.
  • Turings zweite Aufgabe besteht darin, diese enorm lange Zeichenkette von Symbolen zu "gödelisieren", indem sie Gödels Technik verwendet, den Symbolen Primzahlen zuzuweisen und die Primzahlen nach Gödels Methode in Primzahlen zu erhöhen.

Komplikationen

Turings Beweis ist durch eine große Anzahl von Definitionen kompliziert und wird mit dem verwechselt, was Martin Davis "kleine technische Details" und "...technische Details [die] wie gegeben falsch sind" (Davis' Kommentar in Undecidable , S. 115) nannte. Turing selbst veröffentlichte 1938 "A Correction": "Der Autor ist P. Bernays zu Dank verpflichtet, dass er auf diese Fehler hingewiesen hat" ( Undecidable , S. 152).

Insbesondere der dritte Beweis ist in seiner ursprünglichen Form durch technische Fehler stark beeinträchtigt. Und selbst nach Bernays' Vorschlägen und Turings Korrekturen blieben Fehler in der Beschreibung der Universalmaschine . Und da Turing sein ursprüngliches Papier nicht korrigieren konnte, erinnert ein Teil des Textes verwirrend an Turings mangelhafte erste Anstrengung.

Bernays' Korrekturen finden sich in Undecidable , S. 152–154; das Original ist zu finden als "On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction", Proceedings of the London Mathematical Society (2), 43 (1938), 544-546.

Die Online-Version von Turings Aufsatz enthält diese Korrekturen in einem Nachtrag; Korrekturen an der Universalmaschine müssen jedoch in einer Analyse von Emil Post gefunden werden .

Der einzige Mathematiker, der den Details des Beweises große Aufmerksamkeit widmete, war zunächst Post (vgl. Hodges S. 125) – vor allem, weil er gleichzeitig zu einer ähnlichen Reduktion des "Algorithmus" auf primitive maschinenähnliche Handlungen gelangt war, so dass er nahm ein persönliches Interesse an dem Beweis. Seltsamerweise (vielleicht hat der Zweite Weltkrieg eingegriffen) brauchte Post etwa zehn Jahre, um es im Anhang zu seinem Aufsatz Recursive Unsolvability of a Problem von Thue , 1947 (nachgedruckt in Undecidable , S. 293), zu analysieren.

Andere Probleme stellen sich: In seinem Anhang kommentierte Post indirekt die Schwierigkeit des Papiers und direkt seine "Umrissnatur" (Post in Undecidable , S. 299) und "intuitive Form" der Beweise ( ebd .). Post musste verschiedene Punkte ableiten:

Wenn unsere Kritik richtig ist, heißt eine Maschine kreisfrei, wenn sie eine Turing-Rechenmaschine ist, die unendlich viele Nullen und Einsen druckt. Und die beiden fraglichen Theoreme von Turing sind in Wirklichkeit die folgenden. Es gibt keine Turing ... Maschine, die, wenn sie mit einer beliebigen positiven ganzen Zahl n versorgt wird, bestimmt, ob n der DN einer Turing-Rechenmaschine ... ist, die kreisfrei ist. [Zweitens] Es gibt keine Turing-Konventionsmaschine, die, wenn sie mit einer beliebigen positiven ganzen Zahl n versorgt wird, bestimmt, ob n der DN einer Turing-Rechenmaschine ist, die jemals ein gegebenes Symbol (z. B.) druckt. (Beitrag in Unentscheidbar , S. 300)

Jeder, der jemals versucht hat, die Zeitung zu lesen, wird Hodges' Beschwerde verstehen:

Das Blatt begann attraktiv, stürzte sich aber bald (in typischer Turing-Manier) in ein Dickicht obskurer deutscher Gotik, um seinen Lehrtisch für die Universalmaschine zu entwickeln. Die letzten, die einen Blick darauf werfen würden, wären die angewandten Mathematiker, die auf praktische Berechnungen zurückgreifen mussten... (Hodges S. 124)

Glossar der von Turing verwendeten Begriffe

1 berechenbare Zahl — eine Zahl, deren Dezimalzahl von einer Maschine berechenbar ist (dh mit endlichen Mitteln wie einem Algorithmus)

2 M — eine Maschine mit einer endlichen Befehlstabelle und einem Abtast-/Druckkopf. M bewegt ein unendliches Band, das in Quadrate unterteilt ist, von denen jedes „ein Symbol tragen kann“. Die Maschinenbefehle sind nur die folgenden: ein Quadrat nach links bewegen, ein Quadrat nach rechts bewegen, auf dem gescannten Quadrat Symbol p drucken, das gescannte Quadrat löschen, wenn das Symbol p ist, dann Anweisung aaa ausführen, wenn das gescannte Symbol nicht p ist dann Anweisung aaa ausführen, wenn das gescannte Symbol keines ist, dann Anweisung aaa ausführen, wenn das gescannte Symbol irgendeine ist, Anweisung aaa [wobei "aaa" eine Anweisungskennung ist] ausführen.

3 Rechenmaschine – ein M, das zwei Arten von Symbolen druckt, Symbole des ersten Typs werden „Figuren“ genannt und sind nur binäre Symbole 1 und 0; Symbole des zweiten Typs sind beliebige andere Symbole.

4 Figuren – Symbole 1 und 0 , auch bekannt als „Symbole der ersten Art“

5 m-Konfiguration — die Befehlskennung, entweder ein Symbol in der Befehlstabelle oder eine Reihe von Symbolen, die die Befehlsnummer auf dem Band der Universalmaschine darstellen (zB "DAAAAA = #5")

6 Symbole zweiter Art — alle anderen Symbole als 1 und 0

7 Rundschreiben — eine erfolglose Rechenmaschine. Es gelingt nicht, die Zahlen 0 oder 1 bis ins Unendliche zu drucken, die binär die Zahl darstellen, die es berechnet

8 circle-free — eine erfolgreiche Rechenmaschine. Es druckt bis ins Unendliche die Zahlen 0 oder 1 , die binär die Zahl darstellen, die es berechnet

9- Sequenz — wie in „von der Maschine berechnete Sequenz“: Symbole der ersten Art, auch Figuren, auch Symbole 0 und 1 genannt.

10 berechenbare Folge — kann von einer kreisfreien Maschine berechnet werden

11 SD – Standardbeschreibung: eine Folge von Symbolen A, C, D, L, R, N, „;“ auf einem Turing-Maschinenband

12 DN — Beschreibungsnummer: eine in eine Zahl umgewandelte SD: 1=A, 2=C, 3 =D, 4=L, 5=R, 6=N, 7=;

13 M(n) — eine Maschine, deren DN die Nummer „n“ ist

14 zufriedenstellend – ein SD oder DN, der eine kreisfreie Maschine darstellt

15 U – eine Maschine, die mit einer „universellen“ Anleitungstabelle ausgestattet ist. Wenn U „mit einem Band versorgt wird, auf dessen Anfang die SD einer Rechenmaschine M geschrieben ist, berechnet U dieselbe Sequenz wie M“.

16 β' —„beta-primed“: Eine sogenannte „Diagonalzahl“ bestehend aus der n-ten Zahl (dh 0 oder 1) der n-ten berechenbaren Folge [auch: die berechenbare Zahl von H, siehe unten ]

17 u — ein unbefriedigendes, dh kreisförmiges, SD

18 s — befriedigend, dh kreisfrei SD

19 D — eine in H enthaltene Maschine (siehe unten). Wenn es mit der SD einer beliebigen Rechenmaschine M geliefert wird, testet D die SD von M und wenn sie kreisförmig ist, markieren Sie sie mit „u“ und wenn sie kreisfrei ist, markieren Sie sie mit „s“

20 H – eine Rechenmaschine. H berechnet B', unterhält R und N. H enthält D und U und eine nicht spezifizierte Maschine (oder einen Prozess), die N und R unterhält und D mit dem äquivalenten SD von N versorgt. E berechnet auch die Zahlen von B' und setzt die Zahlen zusammen von B'.

21 R — eine Aufzeichnung oder Bilanz der Anzahl erfolgreicher (kreisfreier) SD, die von D . getestet wurden

22 N — eine Zahl, die mit 1 beginnt und von der Maschine E in ein SD umgewandelt werden soll. E behält N bei.

23 K — eine Zahl. Der DN von H.

Erforderlich für Beweis Nr. 3

5 m-Konfiguration — die Befehlskennung, entweder ein Symbol in der Befehlstabelle oder eine Reihe von Symbolen, die die Nummer des Befehls auf dem Band der Universalmaschine darstellen (zB "DAAAAA = Befehl #5"). In Turings SD kommt die m-Konfiguration zweimal in jeder Anweisung vor, der String ganz links ist die "aktuelle Anweisung"; die Zeichenfolge ganz rechts ist die nächste Anweisung.

24 vollständige Konfiguration — die Nummer (Abbildung 1 oder 0 ) des gescannten Quadrats, die vollständige Sequenz aller Symbole auf dem Band und die m-Konfiguration (die Befehlskennung, entweder ein Symbol oder eine Zeichenkette, die eine Zahl darstellt, zB "Anweisung DAAAA = #5")

25 RSi(x, y) — "in der vollständigen Konfiguration x von M ist das Symbol auf dem Quadrat y Si; "vollständige Konfiguration" ist Definition #5

26 I(x, y) — "in der vollständigen Konfiguration x von M wird das Quadrat y abgetastet"

27 Kqm(x) — "in der Gesamtkonfiguration x von M ist die Maschinenkonfiguration ( Befehlsnummer ) qm"

28 F(x,y) — "y ist der unmittelbare Nachfolger von x" (folgt Gödels Verwendung von "f" als Nachfolgerfunktion).

29 G(x,y) — "x geht vor y", nicht unbedingt sofort

30 Inst{qi, Sj Sk L ql} ist eine Abkürzung, ebenso wie Inst{qi, Sj Sk R ql} und Inst{qi, Sj Sk N ql} . Siehe unten.

Turing reduziert seinen Befehlssatz auf drei „kanonische Formen“ – eine für Links, Rechts und Bewegungsfreiheit. Si und Sk sind Symbole auf dem Band.

Band Finale
m-config Symbol Betrieb m-config
qi Si PSk, L qm
qi Si PSk, R qm
qi Si PSk, N qm

Zum Beispiel sind die Operationen in der ersten Zeile PSk = PRINT Symbol Sk aus der Sammlung A, C, D, 0, 1, u, v, w, x, y, z, : , dann das Band nach LINKS bewegen.

Diese hat er weiter abgekürzt als: (N1) qi Sj Sk L qm (N2) qi Sj Sk R qm (N3) qi Sj Sk N qm

In Beweis #3 nennt er die erste davon „Inst{qi Sj Sk L ql}“ und zeigt, wie man die gesamte Maschine SD als logische Konjunktion (logisches ODER) schreibt: Diese Zeichenfolge heißt „Des(M)“ , wie in „Beschreibung-von-M“. d. h. wenn die Maschine 0, dann 1 und 0 auf abwechselnden Feldern nach rechts ad infinitum druckt, könnte sie die Tabelle haben (ein ähnliches Beispiel erscheint auf Seite 119):

q1, leer, P0, R, q2
q2, leer, P-leer, R, q3
q3, leer, P1, R, q4
q4, leer, P-leer, R, q1

(Dies wurde mit den „p-blank“-Anweisungen auf die kanonische Form reduziert, sodass sie sich etwas von Turings Beispiel unterscheidet.) Wenn sie in die „Inst( S1 = 0, S2 = 1):

Inst {q1 S0 S1 R q2}
Inst {q2 S0 S0 R q3}
Inst {q3 S0 S2 R q4}
Inst {q4 S0 S0 R q1}

Die Reduzierung auf die Standardbeschreibung (SD) beträgt:

; DADDCRDAA ; DAADDRDAAA ; DAAADDDCCRDAAAA ; DAAAADDRDA ;

Dies stimmt mit seinem Beispiel im Buch überein (zwischen jedem Buchstaben und jeder Zahl befindet sich ein Leerzeichen). Die Universalmaschine U verwendet die alternativen leeren Quadrate als Orte, um "Zeiger" zu setzen.

Verweise

  • Turing, AM (1937), "On Computable Numbers, with an Application to the Entscheidungsproblem", Proceedings of the London Mathematical Society , 2, 42 (1), S. 230–65, doi : 10.1112/plms/s2-42.1. 230
  • Turing, AM (1938), "On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction", Proceedings of the London Mathematical Society , 2, 43 (6), S. 544–6, doi : 10.1112/plms/s2 -43.6.544). ( Online-Version .) Dies ist das epochale Papier, in dem Turing Turing-Maschinen definiert und zeigt, dass das Entscheidungsproblem unlösbar ist.
  • Hans Reichenbach (1947), Elemente der symbolischen Logik , Dover Publications, Inc., New York.
  • Martin Davis (1965), Das Unentscheidbare, Grundlagenpapiere über unentscheidbare Aussagen, unlösbare Probleme und berechenbare Funktionen , Raven Press, New York. Die beiden oben genannten Veröffentlichungen von Post sind in diesem Band enthalten. Andere Papiere sind die von Gödel, Church, Rosser und Kleene.
  • Andrew Hodges (1983), Alan Turing: The Enigma , Simon und Schuster , New York. Vgl. Kapitel "Der Geist der Wahrheit" für eine Geschichte, die zu seinem Beweis führte und eine Diskussion darüber.
  • Torkel Franzén (2005), Gödels Theorem: Ein unvollständiger Leitfaden zu seinem Gebrauch und Missbrauch . AK Peters.