Universal-Turingmaschine - Wikipedia

In der Informatik ist eine universelle Turingmaschine ( UTM ) eine Turingmaschine, die eine willkürliche Turingmaschine auf einer beliebigen Eingabe simulieren kann. Die Universalmaschine erreicht dies im Wesentlichen, indem sie sowohl die Beschreibung der zu simulierenden Maschine als auch deren Eingabe von ihrem eigenen Band liest. Alan Turing stellte die Idee einer solchen Maschine 1936–1937 vor. Dieses Prinzip gilt als Ursprung der Idee eines Computerprogramms mit gespeichertem Programm, das John von Neumann 1946 für das "Electronic Computing Instrument" verwendete, das jetzt von Neumann den Namen trägt: die von Neumann-Architektur. ^[1]

In Bezug auf das Rechnen Komplexität, eine Multi-Tape-Universal-Turingmaschine muss im Vergleich zu den simulierten Maschinen nur um einen logarithmischen Faktor langsamer sein. ^[2]

Einleitung [ edit

Jede Turing-Maschine berechnet aus den eingegebenen Zeichenfolgen über ihrem Alphabet eine bestimmte, fest zu berechnende Teilfunktion. In diesem Sinne verhält es sich wie ein Computer mit einem festen Programm. Wir können jedoch die Aktionstabelle einer beliebigen Turing-Maschine in einer Zeichenfolge codieren. So können wir eine Turing-Maschine erstellen, die auf ihrem Band eine Zeichenfolge erwartet, die eine Aktionstabelle beschreibt, gefolgt von einer Zeichenfolge, die das Eingabeband beschreibt, und das Band berechnet, das die codierte Turing-Maschine berechnet hätte. Turing beschrieb eine solche Konstruktion in seiner Arbeit von 1936 ausführlich:

"Es ist möglich, eine einzelne Maschine zu erfinden, die zur Berechnung einer beliebigen berechenbaren Sequenz verwendet werden kann. Wenn diese Maschine U mit einem Band geliefert wird, auf dessen Anfang die SD ["standard description" of an action table] steht einige Rechenmaschine M dann U berechnet die gleiche Sequenz wie M . " ^[3]

Computer mit gespeichertem Programm [ edit ]

Davis macht ein überzeugendes Argument, dass Turings Vorstellung von dem, was jetzt als "Computer mit gespeichertem Programm" bezeichnet wird, die Platzierung der "Aktionstabelle" "- die Anweisungen für die Maschine - im gleichen" Speicher "wie die Eingabedaten beeinflussten John von Neumanns Konzept des ersten amerikanischen Computers mit diskretem Symbol (im Gegensatz zu analogen Computern) - EDVAC - stark. Davis zitiert Time Zeitschrift zu diesem Zweck, dass "jeder, der an einer Tastatur klopft ... an einer Inkarnation einer Turing-Maschine arbeitet" und dass "John von Neumann [built] über die Arbeit von Alan Turing "(Davis 2000: 193 zitiert Time Magazin vom 29. März 1999).

Davis macht geltend, dass Turings Computer der Automatic Computing Engine (ACE) die Vorstellungen von Mikroprogrammierung (Mikrocode) und RISC-Prozessoren "vorausgesehen" haben (Davis 2000: 188). Knuth zitiert Turings Arbeit auf dem ACE-Computer als "Hardware zur Erleichterung der Verknüpfung von Unterprogrammen" (Knuth 1973: 225); Davis verweist auch auf diese Arbeit als Turings Verwendung eines Hardware- "Stapels" (Davis 2000: 237, Fußnote 18).

Als die Turing-Maschine den Bau von Computern förderte, förderte die UTM die Entwicklung der jungen Computerwissenschaften. Ein früher, wenn nicht der erste, Assembler wurde "von einem jungen Hot-Shot-Programmierer" für die EDVAC vorgeschlagen (Davis 2000: 192). Von Neumanns "erstes ernstes Programm ... [was]um Daten einfach und effizient zu sortieren" (Davis 2000: 184). Knuth stellt fest, dass die im Programm selbst eingebettete Unterprogrammrückgabe nicht in Sonderregistern, sondern von Neumann und Goldstine zuzuschreiben ist. ^[4] Knuth gibt darüber hinaus an

"Die erste Interpretationsroutine kann als" Universal Turing Machine "bezeichnet werden ... Interpretationsroutinen im herkömmlichen Sinne wurden von John Mauchly 1946 in seinen Vorlesungen an der Moore School erwähnt ... Turing beteiligte sich daran Entwicklung auch; Interpretationssysteme für den Pilot-ACE-Computer wurden unter seiner Regie geschrieben "(Knuth 1973: 226).

Davis nennt kurz Betriebssysteme und Compiler als Ergebnis des Begriffs" Programm als Daten "(Davis 2000: 185). .

Bei dieser Bewertung können jedoch Probleme auftreten. Zu der Zeit (Mitte der 1940er bis Mitte der 1950er Jahre) war ein relativ kleiner Forscherkader eng mit der Architektur der neuen "digitalen Computer" beschäftigt. Hao Wang (1954), ein junger Forscher zu dieser Zeit, machte folgende Beobachtung:

Turings Theorie der berechenbaren Funktionen war zwar veraltet, hatte jedoch keinen großen Einfluss auf die umfangreiche Konstruktion digitaler Computer. Diese beiden Aspekte von Theorie und Praxis wurden fast völlig unabhängig voneinander entwickelt. Der Hauptgrund ist zweifellos, dass Logiker sich für Fragen interessieren, die sich radikal von denen unterscheiden, mit denen sich die angewandten Mathematiker und Elektrotechniker hauptsächlich befassen. Es kann jedoch nicht verwunderlich sein, dass die gleichen Konzepte in den beiden Entwicklungen oft durch unterschiedliche Begriffe ausgedrückt werden. "(Wang 1954, 1957: 63)

Wang hoffte, dass sein Artikel die beiden" verbinden würde Ansätze. "In der Tat bestätigt Minsky dies:" Die erste Formulierung der Turing-Maschinentheorie in computerähnlichen Modellen erscheint in Wang (1957) "(Minsky 1967: 200). Minsky demonstriert weiterhin die Turing-Äquivalenz einer Gegenmaschine.

In Bezug auf die Reduzierung von Computern auf einfache Turing-Äquivalentmodelle (und umgekehrt) ist Minskys Bezeichnung von Wang als "die erste Formulierung" offen für Diskussionen. Während sowohl Minskys Artikel von 1961 als auch Wangs Artikel von 1957 von Shepherdson und Sturgis (1963) zitiert werden, zitieren und fassen sie die Arbeit der europäischen Mathematiker Kaphenst (1959), Ershov (1959) und Péter (1958) in einigen Details zusammen. Die Namen der Mathematiker Hermes (1954, 1955, 1961) und Kaphenst (1959) erscheinen in den Bibliographien sowohl von Sheperdson-Sturgis (1963) als auch von Elgot-Robinson (1961). Zwei weitere wichtige Namen sind die kanadischen Forscher Melzak (1961) und Lambek (1961). Für viel mehr sehen Sie Turingmaschinenäquivalente; Referenzen finden Sie auf der Registermaschine.

Mathematische Theorie [ edit ]

Mit dieser Kodierung von Aktionstabellen als Strings wird es Turing-Maschinen prinzipiell möglich, Fragen zum Verhalten anderer Turing-Maschinen zu beantworten. Die meisten dieser Fragen sind jedoch unentscheidbar, so dass die betreffende Funktion nicht mechanisch berechnet werden kann. Beispielsweise wurde das Problem der Feststellung, ob eine beliebige Turing-Maschine bei einer bestimmten Eingabe oder bei allen als Halte-Problem bezeichneten Eingaben angehalten wird, im Turing-Originalpapier im Allgemeinen als nicht entscheidbar befunden. Der Satz von Rice zeigt, dass jede nicht triviale Frage über die Leistung einer Turingmaschine unentscheidbar ist.

Eine universelle Turing-Maschine kann jede rekursive Funktion berechnen, eine beliebige rekursive Sprache bestimmen und jede rekursiv aufzählbare Sprache akzeptieren. Nach der Church-Turing-These sind die von einer universellen Turing-Maschine lösbaren Probleme genau jene Probleme, die mit einem Algorithmus von oder einer effektiven Berechnungsmethode gelöst werden können, um eine vernünftige Definition dieser Ausdrücke zu ermöglichen . Aus diesen Gründen dient eine universelle Turingmaschine als Standard zum Vergleich von Computersystemen, und ein System, das eine universelle Turingmaschine simulieren kann, wird als Turing complete bezeichnet.

Eine abstrakte Version der universellen Turingmaschine ist die Universalfunktion, eine berechenbare Funktion, mit der jede andere berechenbare Funktion berechnet werden kann. Der UTM-Theorem beweist das Vorhandensein einer solchen Funktion.

Effizienz [ edit ]

Ohne Verlust der Allgemeinheit kann davon ausgegangen werden, dass die Eingabe der Turing-Maschine im Alphabet {0, 1} liegt; Jedes andere endliche Alphabet kann über {0, 1} kodiert werden. Das Verhalten einer Turingmaschine M wird durch ihre Übergangsfunktion bestimmt. Diese Funktion kann einfach als Zeichenfolge über dem Alphabet {0, 1} codiert werden. Die Größe des Alphabets von M die Anzahl der Bänder und die Größe des Zustandsraums können der Tabelle der Übergangsfunktion entnommen werden. Die unterscheidbaren Zustände und Symbole können durch ihre Position identifiziert werden, z. Die ersten beiden Zustände können vereinbarungsgemäß die Start- und Stop-Zustände sein. Folglich kann jede Turing-Maschine als Zeichenfolge über dem Alphabet {0, 1} codiert werden. Außerdem erklären wir, dass jede ungültige Codierung einer trivialen Turing-Maschine zugeordnet wird, die sofort angehalten wird, und dass jede Turing-Maschine eine unendliche Anzahl von Codierungen haben kann, indem die Codierung mit einer beliebigen Anzahl von (etwa) 1-Zeichen am Ende aufgefüllt wird, genau wie Kommentare Arbeit in einer Programmiersprache. Es sollte nicht überraschen, dass wir diese Kodierung erreichen können, wenn eine Gödel-Zahl und eine rechnerische Äquivalenz zwischen Turing-Maschinen und μ-rekursiven Funktionen vorhanden sind. In ähnlicher Weise gehört unsere Konstruktion zu jeder binären Saite α einer Turing-Maschine M _α .

Ausgehend von der obigen Codierung zeigten FC Hennie und RE Stearns 1966, dass bei einer Turing-Maschine M _α ein Eingang angehalten wurde x N N Schritte, dann gibt es eine Multi-Tape-Universal-Turingmaschine, die an Eingängen anhält α x (auf verschiedenen Bändern angegeben) in CN log ] N wobei C eine maschinenspezifische Konstante ist, die nicht von der Länge der Eingabe abhängt x hängt aber von M ' ab. s Alphabetgröße, Anzahl der Bänder und Anzahl der Zustände. Tatsächlich ist dies ein ${\displaystyle \mathcal{O}(N\log \; <!--\; \; -->NN}$ -Simulation unter Verwendung der Big O-Notation von Donald Knuth. 19659041] Kleinste Maschinen [ edit ]

Als Alan Turing auf die Idee einer Universalmaschine kam, dachte er an das einfachste Rechenmodell, das alle möglichen Funktionen berechnet, die berechnet werden können . Claude Shannon stellte 1956 erstmals explizit die Frage, nach einer möglichst kleinen universellen Turingmaschine zu suchen. Er zeigte, dass zwei Symbole ausreichend waren, solange genügend Zustände verwendet wurden (oder umgekehrt) und es immer möglich war, Zustände durch Symbole auszutauschen.

Marvin Minsky entdeckte 1962 eine 7-State-Universal-Turingmaschine mit 4 Symbolen und 2-Tag-Systemen. Andere kleine universelle Turingmaschinen wurden seitdem von Yurii Rogozhin und anderen gefunden, indem sie diesen Ansatz der Tag-Systemsimulation erweitert haben. Wenn wir mit m n ) die Klasse von UTMs mit m Staaten und n Symbolen bezeichnen, wurden die folgenden Tupel gefunden: (15, 2), (9, 3), (6, 4), (5, 5), (4, 6), (3, 9) und (2, 18). ^[6][7][8] Rogoschins (4, 6) Die Maschine verwendet nur 22 Befehle, und es ist keine Standard-UTM mit geringerer beschreibender Komplexität bekannt.

Durch die Verallgemeinerung des Turing-Standardmodells werden jedoch noch kleinere UTMs zugelassen. Eine solche Verallgemeinerung besteht darin, ein unendlich wiederholtes Wort auf einer oder beiden Seiten der Turing-Maschineneingabe zuzulassen, wodurch die Definition der Universalität erweitert wird und als "halbschwache" bzw. "schwache" Universalität bezeichnet wird. Für die (6, 2), (3, 3) und (2, 4) Zustand-Symbol-Paare wurden kleine, schwach universelle Turingmaschinen gegeben, die den Zellularautomaten nach Regel 110 simulieren. ^[9] Der Universalitätsnachweis für Wolfram 2 Zustand 3-Symbol Turing-Maschine erweitert den Begriff der schwachen Universalität weiter, indem bestimmte nicht periodische Anfangskonfigurationen zugelassen werden. Andere Varianten des Standard-Turing-Maschinenmodells, die kleine UTMs ergeben, umfassen Maschinen mit mehreren Bändern oder Bändern mit mehreren Abmessungen und Maschinen, die mit einem endlichen Automaten gekoppelt sind.

Maschinen ohne interne Zustände [ edit ]

Wenn Sie mehrere Köpfe auf der Turing-Maschine zulassen, können Sie eine Turing-Maschine ohne interne Zustände verwenden. Die "Zustände" werden als Teil des Bandes codiert. Betrachten Sie beispielsweise ein Band mit 6 Farben: 0, 1, 2, 0A, 1A, 2A. Betrachten Sie ein Band wie 0,0,1,2,2A, 0,2,1, bei dem sich eine 3-Kopf-Turingmaschine über dem Tripel (2,2A, 0) befindet. Die Regeln wandeln dann ein beliebiges Triple in ein anderes Triple um und bewegen die drei Köpfe nach links oder rechts. Beispielsweise können die Regeln (2,2A, 0) in (2,1,0) konvertieren und den Kopf nach links verschieben. In diesem Beispiel verhält sich die Maschine also wie eine 3-Farben-Turingmaschine mit den internen Zuständen A und B (durch keinen Buchstaben dargestellt). Der Fall für eine 2-Kopf-Turingmaschine ist sehr ähnlich. So kann eine 2-Kopf-Turingmaschine mit 6 Farben universell sein. Es ist nicht bekannt, wie viele Farben für eine Mehrkopf-Turingmaschine am geringsten sind, oder ob eine 2-Farben-Universal-Turingmaschine mit mehreren Köpfen möglich ist. Dies bedeutet auch, dass die Umschreibungsregeln von Turing abgeschlossen sind, da die Dreifachregeln den Umschreibungsregeln entsprechen. Wenn das Band auf zwei Dimensionen ausgedehnt wird, wobei ein Kopf einen Buchstaben und seine 8 Nachbarn abtastet, werden nur zwei Farben benötigt, da beispielsweise eine Farbe in einem vertikalen Dreifachmuster wie 110 codiert werden kann.

Beispiel für die Codierung von Universalmaschinen [ edit ]

Für diejenigen, die die Herausforderung annehmen würden, eine UTM genau als Turing zu entwerfen, siehe den Artikel von Davies in Copeland (2004: 103ff.) ). Davies korrigiert die Fehler im Original und zeigt, wie ein Probelauf aussehen würde. Er behauptet, eine (etwas vereinfachte) Simulation erfolgreich durchgeführt zu haben.

Das folgende Beispiel stammt von Turing (1936). Weitere Informationen zu diesem Beispiel finden Sie auf der Seite Beispiele für Turingmaschinen.

Turing verwendete sieben Symbole {A, C, D, R, L, N; } um jedes 5-Tupel zu kodieren; Wie im Artikel Turing-Maschine beschrieben, sind seine 5 Tupel nur vom Typ N1, N2 und N3. Die Anzahl jeder "m-Konfiguration" (Befehl, Zustand) wird durch "D" gefolgt von einer unären Folge von A dargestellt, z. "q3" = DAAA. In ähnlicher Weise codiert er die leeren Symbole als "D", das Symbol "0" als "DC", das Symbol "1" als DCC usw. Die Symbole "R", "L" und "N" bleiben unverändert ist.

Nach der Codierung wird jedes 5-Tupel in einer Zeichenfolge in der folgenden Reihenfolge "zusammengesetzt":

Aktuelle m-Konfiguration	Bandsymbol	Druckvorgang	Bandbewegung	Endgültige m-Konfiguration		Aktueller m-Konfigurationscode	Bandsymbolcode	Druckoperationscode	Bandbewegungscode	Endgültiger m-Konfigurationscode	Zusammengesetzter 5-Tupel-Code
q1	leer	P0 19659070] R	q2		DA	D	DC 19659070] R	DAA	DADDCRDAA
q2	leer	E 19659070] R	q3		DAA	D	D 19659070] R	DAAA	DAADDRDAAA
q3	leer	P1 19659070] R	q4		DAAA	D	DCC 19659070] R	DAAAA	DAAADDCCRDAAAA
q4	leer	E 19659070] R	q1		DAAAA	D	D 19659070] R	DA	DAAAADDRDA

Schließlich werden die Codes für alle vier 5-Tupel zu einem Code zusammengefügt, der mit ";" und getrennt durch ";" d.h.

; DADDCRDAA ; DAADDRDAAA ; DAAADDCCRDAAAA ; DAAAADDRDA

. Quadrate "- die" E-Quadrate "(die zum Löschen neigen) bleiben leer. Die Endmontage des Codes auf dem Band für die U-Maschine besteht darin, zwei spezielle Symbole ("e") nacheinander zu platzieren, dann den Code auf abwechselnden Quadraten aufzuteilen und schließlich das Doppelpunkt-Symbol ". :: "(Leerzeichen sind hier mit". "Dargestellt):

ee. ; .DADDCRDAA ; .DAADDRDAAA ; .DAAADDCCRDAAAA . . . .....

Die Aktionstabelle (Status-Übergangstabelle) des U-Computers ist für die Dekodierung der Symbole verantwortlich. Turings Aktionstabelle verfolgt ihren Platz mit Markierungen "u", "v", "x", "y", "z", indem er sie in "E-Quadrate" rechts neben "dem markierten Symbol" platziert - zum Beispiel , um den aktuellen Befehl zu markieren z wird rechts von ";" x behält den Platz in Bezug auf die derzeitige "m-configuration" DAA. Die Aktionstabelle des U-Computers wird diese Symbole im Verlauf der Berechnung hin und her bewegen (löschen und an verschiedenen Orten platzieren):

ee. ; . D.A.D.D.C.R.D.A.A. ; z DAA x DDRDAAA ; .DAAADDCCRDAAAA ; .DAAAADDRDA . ..

Turings Action-Table für seine U-Maschine ist sehr involviert.

Eine Reihe anderer Kommentatoren (insbesondere Penrose 1989) bietet Beispiele für die Kodierung von Anweisungen für die Universal-Maschine. Wie Penrose verwenden die meisten Kommentatoren nur Binärsymbole, d. H. Nur die Symbole {0, 1} oder {Leerzeichen | }. Penrose geht noch weiter und schreibt seinen gesamten U-Maschinencode aus (Penrose 1989: 71–73). Er behauptet, dass es sich wirklich um einen U-Maschinencode handelt, eine enorme Zahl, die fast zwei volle Seiten von Einsen und Nullen umfasst. Für Leser, die an einfacheren Kodierungen für die Post-Turing-Maschine interessiert sind, kann die Diskussion von Davis in Steen (Steen 1980: 251ff) hilfreich sein.

Asperti und Ricciotti beschrieben eine Multi-Tape-UTM, die durch das Erstellen von Elementarmaschinen mit sehr einfacher Semantik definiert wird, anstatt explizit die vollständige Aktionstabelle anzugeben. Dieser Ansatz war ausreichend modular, um die Richtigkeit der Maschine im Matita-Proofassistenten formal nachzuweisen.

Programmierung von Turingmaschinen [ edit ]

Verschiedene übergeordnete Sprachen können in eine Turing-Maschine integriert werden. Beispiele umfassen Laconic und Turing Machine Descriptor. ^[10][11]

Siehe auch [ edit ]

Referenzen [ edit

1. Der Universalcomputer: die Straße von Leibniz nach Turing (2017)
   


2. Arora und Barak, 2009, Satz 1.9
   


3. Boldface ersetzt Skript. Turing 1936 in Davis 1965: 127–128. Ein Beispiel für Turings Vorstellung von SD ist am Ende dieses Artikels angegeben.
   


4. Insbesondere: Burks, Goldstine, von Neumann (1946), Vorläufige Erörterung des logischen Designs eines elektronischen Computerinstruments neu gedruckt in Bell und Newell 1971
   


5. ^ Arora und Barak, 2009, Satz 1.9
   


6. ^ Rogozhin, 1996
   


7. ^ Kudlek und Rogozhin, 2002
   


8. ^ Neary and Woods, 2009
   


9. ^ Neary and Woods, 2009b
   


10. ^ "Shtetl-optimiert" Blog-Archiv "Die 8000th Busy Beaver-Nummer eludiert ZF-Satztheorie: neu Papier von Adam Yedidia und mir ". www.scottaaronson.com . 2016-12-29 .
    


11. ^ "Laconic - Esolang". esolangs.org . Abgerufen 2016-12-29 .
    

Allgemeine Angaben

Original Paper

Seminal Papers

• Hennie, F. C .; Stearns, R. E. (1966). "Zwei-Band-Simulation von Multitape-Turingmaschinen". Zeitschrift der ACM . 13 (4): 533. doi: 10.1145 / 321356.321362.

Implementierung

Formale Verifizierung

Weitere Referenzen

• Copeland, Jack, Hrsg. (2004), The Essential Turing: wegweisende Schriften im Bereich Computing, Logik, Philosophie, künstliche Intelligenz und künstliches Leben plus Die Geheimnisse der Enigma Oxford UK: Oxford University Press, ISBN 0-19-825079-7


• Davis, Martin (1980), "Was ist Berechnung?", In Steen, Lynn Arthur, Mathematics Today: Zwölf informelle Essays New York: Vintage Books (Zufallshaus), ISBN 978-0 -394-74503-9 .


• Davis, Martin (2000), Motoren der Logik: Mathematiker und der Ursprung des Computers (1. Aufl.), New York, NY: WW Norton & amp; Company, ISBN 0-393-32229-7, (pb.)


• Goldstine, Herman H .; von Neumann, John. Planung und Codierung der Probleme für ein elektronisches Datenverarbeitungsgerät . Institute for Advanced Study (Ausg. 1947). Princeton
  Bell, C. Gordon; Newell, Allen (1971). Computerstrukturen: Lesungen und Beispiele (Nachdruck). New York: McGraw-Hill Book Company. S. 92–119. ISBN 0-07-004357-4.


• Herken, Rolf (1995), Die Universal-Turing-Maschine - Eine Halbjahresübersicht Springer Verlag, ISBN 3-211-82637-8


• Knuth, Donald E .. (1968), Die Kunst der Computerprogrammierung Zweite Auflage, Band 1 / Fundamental Algorithms (2. 1973) (Erste Ausgabe), Addison-Wesley Publishing Company [19659171DieerstevonKnuthsReihevondreiTexten


• Kudlek, Manfred; Rogozhin, Yurii (2002), "Eine universelle Turingmaschine mit 3 Zuständen und 9 Symbolen", LNCS Springer, 2295 : 311–318, doi: 10.1007 / 3-540- 46011-x_27


• Minsky, Marvin (1962), "Größe und Struktur von Universal-Turingmaschinen unter Verwendung von Markierungssystemen, Rekursive Funktionstheorie", Proc. Symp. Pure Mathematics Providence RI: American Mathematical Society, 5 : 229–238


• Neary, Turlough; Woods, Damien (2009), "Vier kleine Universal-Turingmaschinen", Fundamenta Informaticae 91 (1)


• Neary, Turlough; Woods, Damien (2009b), Kleine schwach universelle Turingmaschinen 17. Internationales Symposium über Grundlagen der Berechnungstheorie, Springer LNCS 5699, S. 262–273


• Penrose, Roger (1989), The Emperor's New Mind Oxford (Vereinigtes Königreich): Oxford University Press, ISBN 0-19-851973-7, (hc.), (S.)


• Rogozhin, Yurii (1996), "Small Universal Turing Machines", Theoretical Computer Science 168 (2): 215–240, doi: 10.1016 / S0304-3975 (96) 00077-1


• Shannon, Claude (1956), "A Universal-Turingmaschine mit zwei internen Zuständen ", Automatenstudien Princeton, NJ: Princeton University Press, S. 157–165


• Turing, AM (1936), "Über berechenbare Zahlen mit einer Anwendung auf das Entscheidungsproblem", Verfahren der London Mathematical Society 2, 42 S. 230–65, doi: 10.1112 / plms / s2-42.1.230


• Turing, AM (1938), "Über berechenbare Zahlen mit einer Anwendung auf das Entscheidungsproblem: Eine Korrektur", Verfahren der London Mathematical Society 2 (veröffentlicht 1937), 43 (6), S. 544–6, doi: 10.1112 / plms / s2-43.6.544
  Davis, Martin (1965). Das Unentscheidbare (Nachdruck). Hewlett, NY: Raven Press. S. 115–154. mit Korrekturen an Turings UTM von Emil Post vgl. Fußnote 11 S. 299 CS1 Pflege: Zusatztext: Autorenliste (Link)