Turingmaschine

Klassen von Automaten

Eine Turingmaschine ist ein mathematisches Berechnungsmodell, das eine abstrakte Maschine ^{[ 1 ]} beschreibt , die Symbole auf einem Band gemäß einer Regeltabelle manipuliert. ^{[ 2 ]} Trotz der Einfachheit des Modells ist es in der Lage, jeden beliebigen Computeralgorithmus zu implementieren . ^{[ 3 ]}

Die Maschine arbeitet mit einem unendlichen ^{[ 4 ]} Speicherband, das in diskrete Zellen ^{[ 5 ]} unterteilt ist . Jede Zelle kann ein einzelnes Symbol aus einer endlichen Menge von Symbolen, dem sogenannten Maschinenalphabet , aufnehmen . Sie besitzt einen „Lesekopf“, der sich während des gesamten Vorgangs über einer dieser Zellen befindet, und einen „Zustand“, der aus einer endlichen Menge von Zuständen ausgewählt wird. In jedem Schritt liest der Lesekopf das Symbol in seiner Zelle. Anschließend schreibt die Maschine, basierend auf dem Symbol und ihrem aktuellen Zustand, ein Symbol in dieselbe Zelle und bewegt den Lesekopf einen Schritt nach links oder rechts ^{[ 6 ]} oder bricht die Berechnung ab. Die Wahl des zu schreibenden Symbols, der Bewegungsrichtung des Lesekopfs und des Abbruchs basiert auf einer endlichen Tabelle, die für jede Kombination aus aktuellem Zustand und gelesenem Symbol die entsprechende Aktion festlegt. Wie bei einem realen Computerprogramm kann auch eine Turingmaschine in eine Endlosschleife geraten , die niemals beendet wird.

Die Turingmaschine wurde 1936 von Alan Turing erfunden [ ^{7 , 11 ] , der sie} als „a-Maschine“ (automatische Maschine) bezeichnete [12]. ^{Turings Doktorvater ,} Alonzo Church , prägte später in einer Rezension den Begriff „Turingmaschine“ ^{[ 13 ]} . Mit diesem Modell konnte Turing zwei Fragen verneinen:

• Gibt es eine Maschine, die feststellen kann, ob eine beliebige Maschine auf ihrem Band "zirkuläre" Prozesse abläuft (z. B. einfriert oder ihre Rechenaufgabe nicht fortsetzt)?
• Gibt es eine Maschine, die feststellen kann, ob eine beliebige Maschine auf ihrem Band jemals ein bestimmtes Symbol ausgibt? ^{[ 14 ] [ 15 ]}

Indem er eine mathematische Beschreibung eines sehr einfachen Geräts lieferte, das beliebige Berechnungen durchführen kann, konnte er Eigenschaften der Berechnung im Allgemeinen beweisen – und insbesondere die Unberechenbarkeit des Entscheidungsproblems (ob jede mathematische Aussage beweisbar oder widerlegbar ist). ^{[ 16 ]}

Turingmaschinen bewiesen die Existenz fundamentaler Grenzen der Leistungsfähigkeit mechanischer Berechnungen. ^{[ 3 ]}

Obwohl sie beliebige Berechnungen ausführen können, ist ihr minimalistisches Design für die praktische Anwendung zu langsam: Computer in der realen Welt basieren auf anderen Designs, die im Gegensatz zu Turingmaschinen einen Direktzugriffsspeicher verwenden .

Turing-Vollständigkeit bezeichnet die Fähigkeit eines Berechnungsmodells oder eines Befehlssystems, eine Turingmaschine zu simulieren. Eine Turing-vollständige Programmiersprache kann theoretisch alle von Computern ausführbaren Aufgaben beschreiben; nahezu alle Programmiersprachen sind Turing-vollständig, wenn man die Beschränkungen des endlichen Speichers außer Acht lässt.

Eine Turingmaschine ist ein idealisiertes Modell einer Zentraleinheit (CPU), die alle Datenverarbeitungsvorgänge eines Computers steuert. Die kanonische Turingmaschine verwendet sequenziellen Speicher zur Datenspeicherung. Typischerweise wird dieser sequentielle Speicher als unendlich langes Band dargestellt, auf dem die Maschine Lese- und Schreibvorgänge durchführen kann.

Im Kontext der formalen Sprachtheorie ist eine Turingmaschine ( ein Automat ) in der Lage, eine beliebige Teilmenge gültiger Zeichenketten eines Alphabets aufzuzählen . Eine solche Menge von Zeichenketten wird als rekursiv aufzählbare Sprache bezeichnet . Die Turingmaschine kann äquivalent als Modell definiert werden, das gültige Eingabezeichenketten erkennt, anstatt Ausgabezeichenketten aufzuzählen.

Bei einer gegebenen Turingmaschine M und einer beliebigen Zeichenkette s lässt sich im Allgemeinen nicht vorhersagen, ob M schließlich s erzeugen wird . Dies liegt daran, dass das Halteproblem unlösbar ist, was weitreichende Konsequenzen für die theoretischen Grenzen des Rechnens hat.

Eine Turingmaschine, die jede andere Turingmaschine simulieren kann, wird als universelle Turingmaschine (UTM oder einfach universelle Maschine) bezeichnet. Ein weiterer mathematischer Formalismus mit ähnlicher „universeller“ Natur , der Lambda-Kalkül , wurde von Alonzo Church eingeführt . Churchs Arbeit verknüpfte sich mit Turings Forschung und bildete die Grundlage für die Church-Turing-These . Diese These besagt, dass Turingmaschinen, der Lambda-Kalkül und andere ähnliche Formalismen der Berechnung den informellen Begriff effektiver Methoden in Logik und Mathematik erfassen und somit ein Modell liefern, mit dem man mathematisch präzise über einen Algorithmus oder eine „mechanische Prozedur“ argumentieren kann, ohne an einen bestimmten Formalismus gebunden zu sein. Die Untersuchung der abstrakten Eigenschaften von Turingmaschinen hat zahlreiche Erkenntnisse in der Informatik , der Berechenbarkeitstheorie und der Komplexitätstheorie hervorgebracht .

In seinem 1948 erschienenen Essay „Intelligente Maschinen“ schrieb Turing, dass seine Maschine aus Folgendem besteht:

…eine unbegrenzte Speicherkapazität in Form eines unendlichen, in Quadrate unterteilten Bandes, auf dem jeweils ein Symbol gedruckt werden kann. Zu jedem Zeitpunkt befindet sich genau ein Symbol in der Maschine; dieses wird als gescanntes Symbol bezeichnet. Die Maschine kann das gescannte Symbol verändern, und ihr Verhalten wird teilweise durch dieses Symbol bestimmt. Die Symbole auf dem Band an anderen Stellen haben jedoch keinen Einfluss auf das Verhalten der Maschine. Das Band kann innerhalb der Maschine vor- und zurückbewegt werden; dies ist eine der elementaren Operationen der Maschine. Jedes Symbol auf dem Band kann daher irgendwann einmal verwendet werden. ^{[ 17 ]}

Die Turingmaschine modelliert mathematisch eine Maschine, die mechanisch auf einem Band arbeitet. Auf diesem Band befinden sich Symbole, die die Maschine mithilfe eines Lesekopfes nacheinander lesen und schreiben kann. Die Operation wird vollständig durch eine endliche Menge elementarer Anweisungen bestimmt, wie beispielsweise: „Im Zustand 42: Wenn das gelesene Symbol 0 ist, schreibe eine 1; wenn das gelesene Symbol 1 ist, wechsle in Zustand 17; im Zustand 17: Wenn das gelesene Symbol 0 ist, schreibe eine 1 und wechsle in Zustand 6“ usw. In seinem Originalartikel („ Über berechenbare Zahlen mit einer Anwendung auf das Entscheidungsproblem “, siehe auch die unten stehenden Literaturangaben ) stellt sich Turing keinen Mechanismus vor, sondern eine Person, die er den „Computer“ nennt und die diese deterministischen mechanischen Regeln sklavisch (oder, wie Turing es ausdrückt, „nachlässig“) ausführt.

Genauer gesagt besteht eine Turingmaschine aus:

• Ein in nebeneinanderliegende Zellen unterteiltes Band . Jede Zelle enthält ein Symbol aus einem endlichen Alphabet. Dieses Alphabet enthält ein spezielles Leerzeichen (hier als „0“ dargestellt) und ein oder mehrere weitere Symbole. Das Band ist beliebig nach links und rechts erweiterbar, sodass der Turingmaschine stets die für ihre Berechnung benötigte Bandlänge zur Verfügung steht. Nicht beschriebene Zellen werden mit dem Leerzeichen gefüllt. In manchen Modellen ist das linke Ende des Bandes mit einem speziellen Symbol markiert; das Band ist dann nach rechts entweder erweiterbar oder unbegrenzt erweiterbar.
• Ein Lesekopf kann Symbole auf dem Band lesen und schreiben und das Band zellenweise nach links und rechts bewegen. Bei manchen Modellen bewegt sich der Lesekopf, während das Band stillsteht.
• Ein Zustandsregister speichert den Zustand der Turingmaschine, einen von endlich vielen. Dazu gehört auch der spezielle Startzustand, mit dem das Zustandsregister initialisiert wird. Diese Zustände, so Turing, ersetzen den „Geisteszustand“, in dem sich eine Person bei der Durchführung von Berechnungen normalerweise befinden würde.
• Eine endliche Tabelle ^{[ 19 ]} von Anweisungen ^{[ 20 ]} , die, gegeben den Zustand (q _i ), in dem sich die Maschine gerade befindet, und das Symbol (a _{j ), das sie auf dem Band liest (das Symbol, das sich gerade unter dem Lesekopf befindet), der Maschine sagt, dass sie} nacheinander Folgendes tun soll (für die 5- Tupel -Modelle):

1. Entweder löschen oder ein Symbol hinzufügen (ein _j durch ein _j1 ersetzen ).
2. _{Bewege den Kopf (der durch d k} beschrieben wird und die Werte 'L' für einen Schritt nach links , 'R' für einen Schritt nach rechts oder 'N' für das Bleiben an derselben Stelle annehmen kann ).
3. Gehen Sie vom gleichen oder einem neuen Zustand wie vorgeschrieben aus (gehen Sie zum Zustand q _i1 ).

In den 4-Tupel-Modellen werden das Löschen oder Schreiben eines Symbols (a _j1 ) und das Bewegen des Lesekopfs nach links oder rechts (d _{k ) als separate Befehle angegeben. Die Tabelle weist die Maschine an, (ia) ein Symbol zu löschen oder zu schreiben} oder (ib) den Lesekopf nach links oder rechts zu bewegen und anschließend (ii) den gleichen oder einen neuen Zustand wie vorgegeben anzunehmen. Die Aktionen (ia) und (ib) dürfen jedoch nicht im selben Befehl ausgeführt werden. In manchen Modellen hält die Maschine an, wenn für die aktuelle Kombination aus Symbol und Zustand kein Eintrag in der Tabelle vorhanden ist; andere Modelle erfordern, dass alle Einträge belegt sind.

Jeder Teil der Maschine (d. h. ihr Zustand, ihre Symbolsammlungen und das jeweils verwendete Band) und ihre Aktionen (wie Drucken, Löschen und Bandbewegung) sind endlich , diskret und unterscheidbar ; erst die unbegrenzte Menge an Band und Laufzeit verleiht ihr einen unbegrenzten Speicherplatz .

In Anlehnung an Hopcroft & Ullman (1979) ^{[ 21 ]} kann eine (Ein-Band-)Turingmaschine formal als ein 7- Tupel definiert werden, wobei ${\displaystyle M=\langle Q,\Gamma ,b,\Sigma ,\delta ,q_{0},F\rangle }$

• ${\displaystyle Q}$ist eine endliche, nichtleere Menge von Zuständen ;
• ${\displaystyle \Gamma }$ist eine endliche, nicht leere Menge von Bandalphabetsymbolen ;
• ${\displaystyle b\in \Gamma }$ist das leere Symbol (das einzige Symbol, das während der Berechnung in jedem Schritt unendlich oft auf dem Band vorkommen darf);
• ${\displaystyle \Sigma \subseteq \Gamma \setminus \{b\}}$ist die Menge der Eingabesymbole , d. h. die Menge der Symbole, die im anfänglichen Bandinhalt vorkommen dürfen;
• ${\displaystyle \delta :(Q\setminus F)\times \Gamma \rightharpoonup Q\times \Gamma \times \{L,R\}}$ist eine partielle Funktion , die Übergangsfunktion genannt wird , wobei L eine Linksverschiebung und R eine Rechtsverschiebung darstellt. Ist für den aktuellen Zustand und das aktuelle Bandsymbol nicht definiert, hält die Maschine an; ^{[ 22 ]} anschaulich gibt die Übergangsfunktion den nächsten Zustand an, der vom aktuellen Zustand aus erreicht wird, welches Symbol das vom Lesekopf angezeigte Symbol überschreiben soll und welche nächste Kopfbewegung erforderlich ist.${\displaystyle \delta }$
• ${\displaystyle q_{0}\in Q}$ist der Ausgangszustand ;
• ${\displaystyle F\subseteq Q}$ist die Menge der Endzustände oder akzeptierenden Zustände . Der anfängliche Bandinhalt wird von akzeptiert , wenn er schließlich in einem Zustand aus anhält .${\displaystyle M}$${\displaystyle F}$

Eine Variante erlaubt „keine Verschiebung“, sagen wir N, als drittes Element der Richtungsmenge . ${\displaystyle \{L,R\}}$

Das 7-Tupel für den 3-Zustands -Busy-Beaver sieht folgendermaßen aus (mehr dazu unter Beispiele für Turingmaschinen ):

• ${\displaystyle Q=\{{\mbox{A}},{\mbox{B}},{\mbox{C}},{\mbox{HALT}}\}}$(Bundesstaaten);
• ${\displaystyle \Gamma =\{0,1\}}$(Zeichen des Bandalphabets);
• ${\displaystyle b=0}$(leeres Symbol);
• ${\displaystyle \Sigma =\{1\}}$(Eingabesymbole);
• ${\displaystyle \delta =}$Siehe Zustandstabelle unten (Übergangsfunktion).
• ${\displaystyle q_{0}={\mbox{A}}}$(Anfangszustand);
• ${\displaystyle F=\{{\mbox{HALT}}\}}$(Endzustände);

Zunächst sind alle Bandzellen mit einem Punkt markiert . ${\displaystyle 0}$

Mit den Worten von van Emde Boas (1990): „Das mengentheoretische Objekt [seine formale Beschreibung mit sieben Tupeln, ähnlich der obigen] liefert nur Teilinformationen darüber, wie sich die Maschine verhalten wird und wie ihre Berechnungen aussehen werden.“ ^{[ 23 ]}

Zum Beispiel,

• Es müssen viele Entscheidungen darüber getroffen werden, wie die Symbole tatsächlich aussehen sollen, und es muss eine absolut sichere Methode gefunden werden, Symbole auf unbestimmte Zeit zu lesen und zu schreiben.
• Die Verschiebevorgänge nach links und nach rechts können den Tonkopf über das Band verschieben, aber beim tatsächlichen Bau einer Turingmaschine ist es praktischer, das Band stattdessen unter dem Tonkopf hin und her gleiten zu lassen.
• Das Band kann endlich sein und bei Bedarf automatisch mit Leerstellen erweitert werden (was der mathematischen Definition am nächsten kommt). Üblicherweise stellt man es sich jedoch als unendlich lang an einem oder beiden Enden vor, wobei es bis auf den explizit vorgegebenen endlichen Abschnitt, auf dem sich der Lesekopf befindet, mit Leerstellen vorgefüllt ist (was in der Praxis natürlich nicht umsetzbar ist). Das Band darf keine feste Länge haben, da dies nicht der gegebenen Definition entspräche und den Rechenumfang der Maschine stark einschränken würde: auf die eines linearen beschränkten Automaten, wenn das Band proportional zur Eingabegröße wäre, oder auf die eines endlichen Automaten, wenn es eine feste Länge hätte.

Definitionen in der Literatur weichen mitunter geringfügig voneinander ab, um Argumente oder Beweise zu vereinfachen oder zu verdeutlichen. Dies geschieht jedoch stets so, dass die resultierende Maschine dieselbe Rechenleistung besitzt. Beispielsweise könnte die Menge von zu geändert werden , wobei N („None“ oder „Keine Operation“) es der Maschine ermöglichen würde, auf derselben Bandzelle zu bleiben, anstatt sich nach links oder rechts zu bewegen. Dies würde die Rechenleistung der Maschine nicht erhöhen. ${\displaystyle \{L,R\}}$${\displaystyle \{L,R,N\}}$

Die gebräuchlichste Konvention stellt jede „Turing-Anweisung“ in einer „Turing-Tabelle“ durch eines von neun 5-Tupeln dar, gemäß der Konvention von Turing/Davis (Turing (1936) ^{[ 24 ]} und Davis (2000) ^{[ 25 ]} ):

(Definition 1): (q _i , S _j , S _k /E/N, L/R/N, q _m )

( aktueller Zustand q _i , gescanntes Symbol S _j , Symbol ausgeben S _k /löschen E /keine N , Band um ein Feld nach links L /rechts R /keine N bewegen , neuer Zustand q _m )

Andere Autoren (Minsky (1967), ^{[ 26 ]} Hopcroft und Ullman (1979), ^{[ 27 ]} Stone (1972), ^{[ 28 ]} verwenden eine andere Konvention, bei der der neue Zustand q _m unmittelbar nach dem gescannten Symbol S _j aufgeführt wird :

(Definition 2): (q _i , S _j , q _m , S _k /E/N, L/R/N)

( aktueller Zustand q _i , gescanntes Symbol S _j , neuer Zustand q _m , Symbol ausgeben S _k /löschen E /keine N , Band um ein Feld nach links L /rechts R /keine N verschieben )

Im Folgenden wird die „Definition 1“ (die Turing/Davis-Konvention) verwendet.

In der folgenden Tabelle erlaubte Turings ursprüngliches Modell nur die ersten drei Zeilen, die er N1, N2 und N3 nannte. ^{[ 29 ]} Er ermöglichte das Löschen des „abgetasteten Quadrats“, indem er ein 0. Symbol S ₀ = „Löschen“ oder „Leerzeichen“ usw. benannte. Er erlaubte jedoch kein Nicht-Drucken, sodass jede Anweisungszeile „Drucksymbol S _k “ oder „Löschen“ enthielt. ^{[ 31 ]} Die Abkürzungen stammen von Turing. ^{[ 32 ]} Nach Turings ursprünglicher Veröffentlichung von 1936–1937 erlaubten Maschinenmodelle alle neun möglichen Typen von Fünf-Tupeln:

Jede Turingtabelle (Anweisungsliste) lässt sich aus den oben genannten neun 5-Tupeln konstruieren. Aus technischen Gründen können die drei nicht druckbaren oder „N“-Anweisungen (4, 5, 6) in der Regel weggelassen werden. Beispiele finden sich unter Beispiele für Turingmaschinen .

Seltener findet man die Verwendung von 4-Tupeln: Diese stellen eine weitere Atomisierung der Turing-Befehle dar. ^{[ 33 ]}

Der Begriff „Zustand“ im Zusammenhang mit Turingmaschinen kann zu Verwirrung führen, da er zwei Bedeutungen haben kann. Die meisten Kommentatoren nach Turing verwendeten „Zustand“ als Bezeichnung für den Namen/die Kennung des aktuell auszuführenden Befehls – also den Inhalt des Zustandsregisters. Turing (1936) unterschied jedoch klar zwischen der Aufzeichnung der sogenannten „m-Konfiguration“ der Maschine und dem „Fortschritt“ der Maschine (oder des Benutzers) während der Berechnung – dem aktuellen Zustand des Gesamtsystems. Die von Turing so genannte „Zustandsformel“ umfasst sowohl den aktuellen Befehl als auch alle Symbole auf dem Band.

Der Fortschritt der Berechnung in jeder Phase wird somit vollständig durch die Anweisungen und die Symbole auf dem Band bestimmt. Das heißt, der Systemzustand lässt sich durch einen einzigen Ausdruck (eine Symbolfolge) beschreiben, der aus den Symbolen auf dem Band, gefolgt von Δ (das an anderer Stelle nicht vorkommen darf) und den Anweisungen besteht. Dieser Ausdruck wird als „Zustandsformel“ bezeichnet.

In einem früheren Teil seiner Arbeit ging Turing noch einen Schritt weiter: Er gibt ein Beispiel, in dem er das Symbol der aktuellen „m-Konfiguration“ – die Bezeichnung der Anweisung – zusammen mit allen Symbolen auf dem Band unter das gescannte Quadrat platziert. ^{[ 35 ]} Er nennt dies die „ vollständige Konfiguration “. ^{[ 36 ]} Um die „vollständige Konfiguration“ in einer Zeile auszugeben, platziert er die Zustandsbezeichnung/m-Konfiguration links neben dem gescannten Symbol.

Eine Variante davon findet sich bei Kleene (1952), der die Schreibweise der Gödel-Zahl des Zustands einer Maschine beschreibt: Er platziert das Symbol der „m-Konfiguration“ q₄ _über dem gescannten Feld, etwa in der Mitte der sechs nicht leeren Felder auf dem Band (siehe Abbildung des Turing-Bandes in diesem Artikel), und zwar rechts neben dem gescannten Feld. ^{[ 37 ]} Kleene bezeichnet „q₄“ selbst jedoch _als „Maschinenzustand“. Hopcroft und Ullman nennen diese Kombination die „momentane Beschreibung“ und folgen der Turing-Konvention, den „aktuellen Zustand“ (Befehlsbezeichnung, m-Konfiguration) links vom gescannten Symbol zu platzieren (S. 149). Die momentane Beschreibung setzt sich also aus den nicht leeren Symbolen links, dem Maschinenzustand, dem vom Lesekopf gescannten Symbol und den nicht leeren Symbolen rechts zusammen.

Beispiel: Gesamtzustand des 3-Zustands-2-Symbol-Busy-Beaver-Algorithmus nach 3 „Zügen“ (aus dem Beispiel „Run“ in der folgenden Abbildung):

1 A 1

Das bedeutet: Nach drei Bewegungen enthält das Band ... 000110000 ..., der Lesekopf scannt die am weitesten rechts liegende 1, und der Zustand ist A. Leerzeichen (in diesem Fall dargestellt durch „0“) können Teil des Gesamtzustands sein, wie hier gezeigt: B 01; das Band enthält eine einzelne 1, aber der Lesekopf scannt die 0 („Leerzeichen“) links davon , und der Zustand ist B.

Der Begriff „Zustand“ im Kontext von Turingmaschinen sollte dahingehend geklärt werden, was beschrieben wird: die aktuelle Anweisung, die Liste der Symbole auf dem Band zusammen mit der aktuellen Anweisung oder die Liste der Symbole auf dem Band zusammen mit der aktuellen Anweisung, die links oder rechts vom gescannten Symbol platziert ist.

Rechts: die obige Tabelle als Zustandsübergangsdiagramm dargestellt.

Große Tabellen sollten in der Regel als solche belassen werden (Booth, S. 74). Sie lassen sich am Computer in Tabellenform leichter simulieren (Booth, S. 74). Bestimmte Konzepte – z. B. Maschinen mit „Reset“-Zuständen und Maschinen mit sich wiederholenden Mustern (vgl. Hill und Peterson, S. 244ff) – lassen sich jedoch in Form einer Zeichnung besser veranschaulichen.

Ob eine Zeichnung eine Verbesserung gegenüber der Tabelle darstellt, muss der Leser im jeweiligen Kontext entscheiden.

Der Leser sollte nochmals darauf hingewiesen werden, dass solche Diagramme eine Momentaufnahme der Tabelle darstellen, nicht den Verlauf einer Berechnung durch Zeit und Raum. Während die Busy Beaver Machine bei jedem Durchlauf stets derselben Zustandsbahn folgt, gilt dies nicht für die Copy Machine, die mit variablen Eingabeparametern versorgt werden kann.

Das Diagramm „Fortschritt der Berechnung“ zeigt den Verlauf des Zustands (der Anweisung) des Busy Beaver-Algorithmus mit drei Zuständen während der Berechnung vom Start bis zum Ende. Ganz rechts ist die Turing-Konfiguration (Kleene-Beschreibung: „Situation“, Hopcroft-Ullman-Beschreibung: „Momentanbeschreibung“) für jeden Schritt dargestellt. Würde die Maschine angehalten und sowohl das Zustandsregister als auch das gesamte Band gelöscht, könnten diese Konfigurationen verwendet werden, um eine Berechnung an jeder beliebigen Stelle fortzusetzen. ^{[ 38 ]}

Viele Maschinen, von denen man annehmen könnte, sie besäßen eine höhere Rechenleistung als eine einfache universelle Turingmaschine, weisen nachweislich keine höhere Rechenleistung auf (Hopcroft und Ullman, S. 159; vgl. Minsky (1967)). Sie mögen zwar schneller rechnen, weniger Speicher benötigen oder einen kleineren Befehlssatz besitzen, aber sie können nicht leistungsfähiger rechnen (d. h. mehr mathematische Funktionen ausführen). (Die Church-Turing-These besagt, dass dies für jede Art von Maschine gilt: Alles, was „berechnet“ werden kann, kann von einer Turingmaschine berechnet werden.)

Eine Turingmaschine entspricht einem einstapeligen Pushdown-Automaten (PDA), der durch die Lockerung des LIFO-Prinzips ( Last-In-First-Out ) flexibler und kompakter gestaltet wurde . Darüber hinaus entspricht eine Turingmaschine auch einem zweistapeligen PDA mit standardmäßiger LIFO-Semantik, indem ein Stapel das Band links vom Lesekopf und der andere Stapel das Band rechts davon modelliert.

Im anderen Extremfall erweisen sich einige sehr einfache Modelle als Turing-äquivalent , d. h. sie besitzen die gleiche Rechenleistung wie das Turingmaschinenmodell.

Gängige äquivalente Modelle sind die Mehrband-Turingmaschine , die Mehrspur-Turingmaschine , Maschinen mit Ein- und Ausgabe sowie die nichtdeterministische Turingmaschine (NDTM) im Gegensatz zur deterministischen Turingmaschine (DTM), bei der die Aktionstabelle höchstens einen Eintrag für jede Kombination aus Symbol und Zustand enthält.

Nur lesbare, rechtsgängige Turingmaschinen sind äquivalent zu DFAs (sowie zu NFAs durch Konvertierung mit Hilfe des NFA-zu-DFA-Konvertierungsalgorithmus ).

Aus praktischen und didaktischen Gründen kann die entsprechende Registermaschine als gewöhnliche Assembler -Programmiersprache verwendet werden .

Eine relevante Frage ist, ob das durch konkrete Programmiersprachen repräsentierte Berechnungsmodell Turing-äquivalent ist. Während die Berechnung eines realen Computers auf endlichen Zuständen basiert und daher keine Turingmaschine simulieren kann, unterliegen Programmiersprachen selbst dieser Einschränkung nicht zwangsläufig. Kirner et al. (2009) haben gezeigt, dass einige Allzweck-Programmiersprachen Turing-vollständig sind, andere hingegen nicht. Beispielsweise ist ANSI C nicht Turing-vollständig, da alle Instanziierungen von ANSI C (unterschiedliche Instanziierungen sind möglich, da der Standard aus Kompatibilitätsgründen bestimmtes Verhalten bewusst undefiniert lässt) einen endlichen Speicherbereich implizieren. Dies liegt daran, dass die Größe von Speicherreferenzdatentypen, sogenannten Zeigern , innerhalb der Sprache zugänglich ist. Andere Programmiersprachen wie Pascal besitzen diese Eigenschaft jedoch nicht, wodurch sie prinzipiell Turing-vollständig sein können. Sie sind nur prinzipiell Turing-vollständig, da die Speicherverwaltung in einer Programmiersprache fehlschlagen kann. Das bedeutet, dass die Programmiersprache Turing-vollständig sein kann, wenn man fehlgeschlagene Speicherverwaltungen ignoriert, die kompilierten, auf einem realen Computer ausführbaren Programme jedoch nicht.

Gleich zu Beginn seiner Arbeit (1936) unterscheidet Turing zwischen einer „automatischen Maschine“ – deren „Bewegung ... vollständig durch die Konfiguration bestimmt wird“ – und einer „Wahlmaschine“:

... deren Bewegung nur teilweise durch die Konfiguration bestimmt wird ... Sobald eine solche Maschine eine dieser mehrdeutigen Konfigurationen erreicht, kann sie nicht weiterlaufen, bis ein externer Bediener eine beliebige Entscheidung getroffen hat. Dies wäre der Fall, wenn wir Maschinen zur Bearbeitung axiomatischer Systeme verwenden würden.

Turing (1936) geht nicht weiter darauf ein, außer in einer Fußnote, in der er beschreibt, wie man eine A-Maschine verwenden kann, um „alle beweisbaren Formeln des Hilbert-Kalküls“ zu finden, anstatt eine Auswahlmaschine zu benutzen. Er sagt: „Angenommen, die Auswahlmöglichkeiten liegen immer zwischen 0 und 1. Jeder Beweis wird dann durch eine Folge von Auswahlen i₁ _, i₂ _, ..., iₙ ₍ i₁ ₌ 0 oder 1, i₂ ₌ 0 oder 1, ..., _{iₙ = 0 oder 1) bestimmt} , und somit legt die Zahl 2ⁿ ⁺ i₁ _2ⁿ⁻¹ + ^{i₂ 2ⁿ⁻²} + ^... + iₙ _den Beweis vollständig fest. Die automatische Maschine führt nacheinander Beweis 1, Beweis 2, Beweis 3, ... aus.“ ^{[ 39 ]}

Dies ist in der Tat die Technik, mit der eine deterministische (d. h. eine -) Turingmaschine dazu verwendet werden kann, die Aktion einer nichtdeterministischen Turingmaschine nachzuahmen ; Turing löste die Angelegenheit in einer Fußnote und scheint sie von weiterer Betrachtung auszuschließen.

Eine Orakelmaschine oder o-Maschine ist eine Turing-a-Maschine, die ihre Berechnung im Zustand „ o “ unterbricht , während sie zur Vervollständigung ihrer Berechnung auf die Entscheidung des „Orakels“ wartet – einer Entität, die Turing nicht näher spezifiziert, „außer dass sie keine Maschine sein kann“ (Turing (1939)). ^{[ 40 ]}

Wie Turing in The Undecidable schrieb (Hervorhebung hinzugefügt): ^{[ 41 ]}

Es ist möglich, eine einzige Maschine zu erfinden, die jede berechenbare Folge berechnen kann . Wenn dieser Maschine U ein Band zugeführt wird, auf dem am Anfang die durch Semikolons getrennte Folge von Quintupeln einer Rechenmaschine M geschrieben steht , dann berechnet U dieselbe Folge wie M.

Das Berechnungsmodell, das Turing seine „universelle Maschine“ – kurz „ U “ – nannte, wird von einigen ^{[ 42 ]} als der grundlegende theoretische Durchbruch angesehen, der zur Idee des speicherprogrammierbaren Computers führte .

Turings Abhandlung ... enthält im Wesentlichen die Erfindung des modernen Computers und einige der damit verbundenen Programmiertechniken.

Hinsichtlich der Rechenkomplexität muss eine universelle Mehrband-Turingmaschine im Vergleich zu den von ihr simulierten Maschinen lediglich um einen logarithmischen Faktor langsamer sein. Dieses Ergebnis wurde 1966 von F. C. Hennie und R. E. Stearns erzielt . ^{[ 44 ] [ 45 ]}

Turingmaschinen sind leistungsfähiger als einige andere Automatenarten, etwa endliche Automaten und Kellerautomaten . Laut der Church-Turing-These sind sie so leistungsfähig wie reale Maschinen und können jede Operation ausführen, die auch ein reales Programm ausführen kann. Dabei wird jedoch außer Acht gelassen, dass eine reale Maschine nur eine endliche Anzahl von Konfigurationen besitzen kann und somit nichts anderes als ein endlicher Automat ist, während einer Turingmaschine unbegrenzter Speicherplatz für ihre Berechnungen zur Verfügung steht.

Es gibt verschiedene Möglichkeiten, zu erklären, warum Turingmaschinen nützliche Modelle realer Computer sind:

• Alles, was ein realer Computer berechnen kann, kann auch eine Turingmaschine berechnen. Zum Beispiel: „Eine Turingmaschine kann jede Art von Unterprogramm simulieren, die in Programmiersprachen vorkommt, einschließlich rekursiver Prozeduren und aller bekannten Parameterübergabemechanismen“ (Hopcroft und Ullman, S. 157). Ein ausreichend großer endlicher Automat kann zudem jeden realen Computer modellieren, wobei die Ein-/Ausgabe vernachlässigt wird. Daher gilt eine Aussage über die Grenzen von Turingmaschinen auch für reale Computer.
• Der Unterschied liegt lediglich in der Fähigkeit einer Turingmaschine, unbegrenzte Datenmengen zu verarbeiten. Bei begrenzter Zeit kann eine Turingmaschine (wie eine reale Maschine) jedoch nur eine endliche Datenmenge verarbeiten.
• Wie bei einer Turingmaschine kann auch bei einer realen Maschine der Speicherplatz nach Bedarf durch den Einbau weiterer Festplatten oder anderer Speichermedien vergrößert werden.
• Beschreibungen realer Maschinenprogramme mithilfe einfacherer abstrakter Modelle sind oft wesentlich komplexer als Beschreibungen mithilfe von Turingmaschinen. Beispielsweise kann eine Turingmaschine, die einen Algorithmus beschreibt, einige hundert Zustände haben, während der entsprechende deterministische endliche Automat (DFA) auf einer gegebenen realen Maschine Billiarden Zustände aufweist. Dies macht die Analyse der DFA-Darstellung praktisch unmöglich.
• Turingmaschinen beschreiben Algorithmen unabhängig von ihrem Speicherbedarf. Zwar ist der Speicher jeder aktuellen Maschine begrenzt, diese Grenze kann jedoch mit der Zeit beliebig erhöht werden. Turingmaschinen ermöglichen es uns, Aussagen über Algorithmen zu treffen, die (theoretisch) unabhängig von Fortschritten in der Architektur konventioneller Computermaschinen unbegrenzt gültig sind.
• Algorithmen, die auf Turing-äquivalenten abstrakten Maschinen laufen, können Datentypen beliebiger Genauigkeit verwenden und müssen sich niemals mit unerwarteten Zuständen auseinandersetzen (einschließlich, aber nicht beschränkt auf Speichermangel ) .

Eine Einschränkung von Turingmaschinen besteht darin, dass sie die Stärken bestimmter Anordnungen nicht gut modellieren. Moderne speicherprogrammierbare Computer sind beispielsweise Instanzen einer spezifischeren Form abstrakter Maschinen, bekannt als Random-Access Stored-Program Machine (RASP). Wie die universelle Turingmaschine speichert auch die RASP ihr „Programm“ in einem „Speicher“ außerhalb der „Befehle“ ihres endlichen Zustandsautomaten. Im Gegensatz zur universellen Turingmaschine verfügt die RASP über eine unendliche Anzahl unterscheidbarer, nummerierter, aber unbegrenzter „Register“ – Speicherzellen, die beliebige ganze Zahlen enthalten können (vgl. Elgot und Robinson (1964), Hartmanis (1971) und insbesondere Cook-Rechow (1973); siehe auch Random-Access Machine ). Der endliche Zustandsautomat der RASP ist mit der Fähigkeit zur indirekten Adressierung ausgestattet (z. B. kann der Inhalt eines Registers als Adresse für ein anderes Register verwendet werden). Das „Programm“ des RASP kann somit jedes Register in der Registersequenz adressieren. Daraus ergibt sich, dass auf Basis der Speicherindizes Rechenoptimierungen möglich sind, die in einer allgemeinen Turingmaschine nicht realisierbar sind. Werden Turingmaschinen daher zur Abschätzung von Laufzeiten verwendet, lässt sich für bestimmte Algorithmen eine falsche untere Schranke beweisen (aufgrund der fälschlichen Vereinfachung durch die Annahme einer Turingmaschine). Ein Beispiel hierfür ist die binäre Suche , ein Algorithmus, der mit dem RASP-Berechnungsmodell schneller arbeitet als mit dem Turingmaschinenmodell.

In den Anfängen der Computertechnik beschränkte sich deren Nutzung typischerweise auf die Stapelverarbeitung , d. h. auf nicht-interaktive Aufgaben, die jeweils Ausgabedaten aus gegebenen Eingabedaten erzeugten. Die Berechenbarkeitstheorie, die die Berechenbarkeit von Funktionen von Eingaben zu Ausgaben untersucht und für die Turingmaschinen erfunden wurden, spiegelt diese Praxis wider.

Seit den 1970er Jahren hat die interaktive Nutzung von Computern deutlich zugenommen. Prinzipiell lässt sich dies modellieren, indem ein externer Agent gleichzeitig mit einer Turingmaschine vom Band liest und darauf schreibt. Dies entspricht jedoch selten der tatsächlichen Interaktion; daher werden zur Beschreibung von Interaktivität üblicherweise Alternativen wie Ein-/Ausgabeautomaten bevorzugt.

Das arithmetische Berechnungsmodell unterscheidet sich vom Turing-Modell in zwei Aspekten: ^{[ 46 ]}

• Im arithmetischen Modell benötigt jede reelle Zahl eine einzelne Speicherzelle, wohingegen im Turing-Modell die Speichergröße einer reellen Zahl von der Anzahl der Bits abhängt, die zu ihrer Darstellung benötigt werden.
• Im arithmetischen Modell können alle grundlegenden arithmetischen Operationen mit reellen Zahlen (Addition, Subtraktion, Multiplikation und Division) in einem einzigen Schritt durchgeführt werden, wohingegen im Turing-Modell die Laufzeit jeder arithmetischen Operation von der Länge der Operanden abhängt.

Manche Algorithmen laufen in einem Modell in Polynomialzeit, im anderen jedoch nicht. Zum Beispiel:

• Der euklidische Algorithmus hat im Turing-Modell eine polynomielle Laufzeit, im arithmetischen Modell jedoch nicht.
• Der Algorithmus, der n Zahlen einliest und diese anschließend durch wiederholtes Quadrieren berechnet , läuft im arithmetischen Modell in Polynomialzeit, nicht aber im Turing-Modell. Dies liegt daran, dass die Anzahl der zur Darstellung des Ergebnisses benötigten Bits exponentiell mit der Eingabegröße wächst.${\displaystyle 2^{2^{n}}}$

Wenn ein Algorithmus jedoch im arithmetischen Modell in Polynomialzeit läuft und die Binärlänge aller beteiligten Zahlen zudem polynomiell in der Länge der Eingabe ist, dann läuft er auch im Turing-Modell stets in Polynomialzeit. Ein solcher Algorithmus wird als stark polynomial bezeichnet .

Robin Gandy (1919–1995) – ein Schüler von Alan Turing (1912–1954) und dessen lebenslanger Freund – verfolgt die Ursprünge des Begriffs der „Rechenmaschine“ zurück zu Charles Babbage (um 1834) und formuliert tatsächlich die „Babbage-These“:

Dass die gesamte Entwicklung und Durchführung der Analyse nun maschinell durchgeführt werden kann .

Gandys Analyse von Babbages analytischer Maschine beschreibt die folgenden fünf Operationen (vgl. S. 52–53):

1. Die arithmetischen Funktionen +, −, ×, wobei − die "echte" Subtraktion bezeichnet: x − y = 0, wenn y ≥ x .
2. Jede Abfolge von Operationen ist eine Operation.
3. Iteration einer Operation (Wiederholung einer Operation P n-mal).
4. Bedingte Iteration (Wiederholung einer Operation P n-mal unter der Bedingung, dass der Test T "erfolgreich" ist).
5. Bedingter Transfer (d. h. bedingter " goto "-Befehl).

Gandy stellt fest, dass „die Funktionen, die mit (1), (2) und (4) berechnet werden können, genau diejenigen sind, die Turing-berechenbar sind .“ ^{[ 48 ]} Er zitiert weitere Vorschläge für „universelle Rechenmaschinen“, darunter die von Percy Ludgate (1909), Leonardo Torres Quevedo (1914), ^{[ 49 ] [ 50 ]} Maurice d’Ocagne (1922), Louis Couffignal (1933), Vannevar Bush (1936) und Howard Aiken (1937). Jedoch:

… der Schwerpunkt liegt auf der Programmierung einer festen, iterierbaren Folge arithmetischer Operationen. Die fundamentale Bedeutung bedingter Iteration und bedingter Übertragung für eine allgemeine Theorie von Rechenmaschinen wird nicht erkannt…

Bezüglich der Hilbertschen Probleme , die der berühmte Mathematiker David Hilbert im Jahr 1900 aufstellte, kursierte ein Aspekt des Problems Nr. 10 bereits seit fast 30 Jahren, bevor er präzise formuliert wurde. Hilberts ursprüngliche Formulierung für Nr. 10 lautet wie folgt:

10. Bestimmung der Lösbarkeit einer diophantischen Gleichung . Gegeben sei eine diophantische Gleichung mit beliebig vielen Unbekannten und rationalen ganzzahligen Koeffizienten. Ziel ist es, ein Verfahren zu entwickeln, mit dem sich in endlich vielen Operationen feststellen lässt, ob die Gleichung in rationalen ganzen Zahlen lösbar ist. Das Entscheidungsproblem ist gelöst , wenn ein Verfahren bekannt ist, mit dem sich für jeden gegebenen logischen Ausdruck in endlich vielen Operationen seine Gültigkeit oder Erfüllbarkeit bestimmen lässt. Das Entscheidungsproblem gilt als das Hauptproblem der mathematischen Logik.

Bis 1922 hatte sich dieser Begriff des „ Entscheidungsproblems “ etwas weiterentwickelt, und H. Behmann stellte fest, dass

Die allgemeinste Form des Entscheidungsproblems lautet wie folgt:

Es bedarf einer eindeutigen, allgemein anwendbaren Vorschrift, die es ermöglicht, in einer endlichen Anzahl von Schritten über die Wahrheit oder Falschheit einer gegebenen rein logischen Aussage zu entscheiden ...

Behmann bemerkt, dass ... das allgemeine Problem äquivalent ist zu dem Problem, zu entscheiden, welche mathematischen Aussagen wahr sind.

Wenn man das Entscheidungsproblem lösen könnte, hätte man ein „Verfahren zur Lösung vieler (oder sogar aller) mathematischer Probleme“.

Auf dem internationalen Mathematikerkongress 1928 präzisierte Hilbert seine Fragen: Erstens, sei die Mathematik vollständig ? Zweitens, sei die Mathematik widerspruchsfrei ? Und drittens, sei die Mathematik entscheidbar ? ^{[ 55 ] [ 56 ]} Die ersten beiden Fragen wurden 1930 von Kurt Gödel auf demselben Kongress beantwortet, auf dem Hilbert (sehr zum Ärger Hilberts) seine Abschiedsrede hielt; die dritte – das Entscheidungsproblem – musste bis Mitte der 1930er Jahre warten.

Das Problem bestand darin, dass eine Antwort zunächst eine präzise Definition von „definitiver allgemein anwendbarer Vorschrift“ erforderte, die der Princeton-Professor Alonzo Church später als „ effektive Berechenbarkeit “ bezeichnen sollte . Eine solche Definition existierte 1928 jedoch noch nicht. In den folgenden sechs bis sieben Jahren entwickelte Emil Post seine Definition eines Arbeiters, der gemäß einer Liste von Anweisungen von Raum zu Raum geht und Spuren schreibt und löscht ^{[ 57 ].} Auch Church und seine beiden Studenten Stephen Kleene und J. B. Rosser taten dies mithilfe von Churchs Lambda-Kalkül und Gödels Rekursionstheorie (1934). Churchs Arbeit (veröffentlicht am 15. April 1936) zeigte, dass das Entscheidungsproblem tatsächlich „unentscheidbar“ war ^{[ 58 ]} und kam Turing um fast ein Jahr zuvor (Turings Arbeit wurde am 28. Mai 1936 eingereicht und im Januar 1937 veröffentlicht). In der Zwischenzeit hatte Emil Post im Herbst 1936 eine kurze Arbeit eingereicht, sodass Turing zumindest Priorität vor Post hatte. Während Church Turings Arbeit begutachtete, hatte Turing Zeit, Churchs Arbeit zu studieren und einen Anhang hinzuzufügen, in dem er einen Beweis skizzierte, dass Churchs Lambda-Kalkül und seine Maschinen die gleichen Funktionen berechnen würden.

Doch Church hatte etwas ganz anderes getan, und in gewisser Hinsicht war sein Ansatz schwächer. … Turings Konstruktion war direkter und lieferte ein Argument von Grundprinzipien ausgehend, wodurch die Lücke in Churchs Beweisführung geschlossen wurde.

Post hatte lediglich eine Definition der Berechenbarkeit vorgeschlagen und Churchs „Definition“ kritisiert, aber nichts bewiesen.

Im Frühjahr 1935 nahm Turing als junger Masterstudent am King's College in Cambridge die Herausforderung an; er war durch die Vorlesungen des Logikers M. H. A. Newman angeregt worden und hatte von ihnen Gödels Werk und das Entscheidungsproblem kennengelernt ... Newman verwendete den Begriff „mechanisch“ ... In seinem Nachruf auf Turing aus dem Jahr 1955 schreibt Newman:

Auf die Frage „Was ist ein ‚mechanischer‘ Prozess?“ gab Turing die charakteristische Antwort „Etwas, das von einer Maschine getan werden kann“ und widmete sich der ihm höchst angenehmen Aufgabe, den allgemeinen Begriff der Rechenmaschine zu analysieren.

Gandy gibt an, dass:

Ich vermute, weiß es aber nicht genau, dass Turing von Beginn seiner Arbeit an den Beweis der Unentscheidbarkeit des Entscheidungsproblems anstrebte. Er erzählte mir, die „Hauptidee“ seiner Arbeit sei ihm im Sommer 1935 auf den Wiesen von Grantchester gekommen. Diese „Hauptidee“ könnte entweder seine Analyse der Berechenbarkeit oder seine Erkenntnis gewesen sein, dass es eine universelle Maschine gab und sich somit ein diagonales Argument zum Beweis der Unlösbarkeit finden ließe.

Gandy hielt Newmans obige Aussage zwar für „irreführend“, doch diese Meinung wird nicht von allen geteilt. Turing interessierte sich zeitlebens für Maschinen: „Als Junge träumte Alan davon, Schreibmaschinen zu erfinden; [seine Mutter] Mrs. Turing besaß eine Schreibmaschine; und er hätte sich durchaus fragen können, was es bedeutet, eine Schreibmaschine als ‚mechanisch‘ zu bezeichnen“ (Hodges, S. 96). Während seiner Promotion in Princeton entwickelte Turing einen Multiplizierer auf Basis der Booleschen Logik (siehe unten). Seine Dissertation mit dem Titel „ Logiksysteme auf Ordinalzahlen “ enthält die folgende Definition einer „berechenbaren Funktion“:

Es wurde bereits erwähnt, dass eine Funktion effektiv berechenbar ist, wenn ihre Werte durch ein rein mechanisches Verfahren ermittelt werden können. Diese Aussage kann wörtlich genommen werden, wobei unter einem rein mechanischen Verfahren ein von einer Maschine durchführbares Verfahren zu verstehen ist. Die Strukturen solcher Maschinen lassen sich in einer bestimmten Normalform mathematisch beschreiben. Die Weiterentwicklung dieser Ideen führt zur Definition einer berechenbaren Funktion durch den Autor und zur Gleichsetzung von Berechenbarkeit und effektiver Berechenbarkeit. Es ist nicht schwierig, wenn auch etwas aufwendig, zu beweisen, dass diese drei Definitionen (die dritte ist der λ-Kalkül) äquivalent sind.

Alan Turing erfand 1936 die „a-Maschine“ (automatische Maschine). ^{[ 7 ]} Turing reichte seine Arbeit am 31. Mai 1936 bei der London Mathematical Society für deren Proceedings ein , ^{[ 62 ]} sie wurde jedoch erst Anfang 1937 veröffentlicht, und Sonderdrucke waren ab Februar 1937 erhältlich. ^{[ 63 ]} Es war Turings Doktorvater, Alonzo Church , der später in einer Rezension den Begriff „Turingmaschine“ prägte. ^{[ 13 ]} Mit diesem Modell konnte Turing zwei Fragen verneinen:

• Gibt es eine Maschine, die feststellen kann, ob eine beliebige Maschine auf ihrem Band "zirkuläre" Prozesse abläuft (z. B. einfriert oder ihre Rechenaufgabe nicht fortsetzt)?
• Gibt es eine Maschine, die feststellen kann, ob eine beliebige Maschine auf ihrem Band jemals ein bestimmtes Symbol ausgibt? ^{[ 14 ] [ 15 ]}

Indem er eine mathematische Beschreibung eines sehr einfachen Geräts lieferte, das zu beliebigen Berechnungen fähig ist, konnte er Eigenschaften der Berechnung im Allgemeinen beweisen – und insbesondere die Unberechenbarkeit des Entscheidungsproblems . ^{[ 16 ]}

Nach seiner Rückkehr nach Großbritannien trug Turing maßgeblich zur Entschlüsselung der deutschen Geheimcodes bei, die mit der Verschlüsselungsmaschine „Enigma“ erstellt wurden. Er war außerdem an der Entwicklung der ACE ( Automatic Computing Engine ) beteiligt. „Turings ACE-Vorschlag war im Grunde in sich abgeschlossen und basierte nicht auf der EDVAC [der US-amerikanischen Initiative], sondern auf seiner eigenen Universalmaschine“ (Hodges, S. 318). Die Diskussionen über Ursprung und Natur dessen, was Kleene (1952) als Turings These bezeichnete, dauern bis heute an . Was Turing jedoch mit seinem Rechenmaschinenmodell bewies, zeigt sich in seiner Arbeit „ Über berechenbare Zahlen mit einer Anwendung auf das Entscheidungsproblem “ (1937).

[dass] das Hilbert-Entscheidungsproblem keine Lösung haben kann ... Ich schlage daher vor zu zeigen, dass es kein allgemeines Verfahren zur Bestimmung geben kann, ob eine gegebene Formel U des Funktionalkalküls K beweisbar ist, d.h. dass es keine Maschine geben kann, die, mit einer beliebigen Formel U dieser Formeln gefüttert, schließlich sagen kann, ob U beweisbar ist.

Turings Beispiel (sein zweiter Beweis): Wenn man nach einem allgemeinen Verfahren fragt, das uns sagt: „Gibt diese Maschine jemals 0 aus?“, dann ist die Frage „unentscheidbar“.

1937, während seiner Arbeit an seiner Doktorarbeit in Princeton, konstruierte Turing einen digitalen (Booleschen) Multiplizierer von Grund auf und fertigte dafür eigene elektromechanische Relais an (Hodges, S. 138). „Alans Aufgabe war es, den logischen Entwurf einer Turingmaschine in einem Netzwerk von relaisgesteuerten Schaltern zu verkörpern …“ (Hodges, S. 138). Während Turing anfangs vielleicht nur neugierig war und experimentierte, wurden in Deutschland von Konrad Zuse (1938) und in den Vereinigten Staaten von Howard Aiken und George Stibitz (1937) ernsthafte Arbeiten in dieselbe Richtung durchgeführt; die Ergebnisse ihrer Forschung wurden im Zweiten Weltkrieg sowohl von den Achsenmächten als auch von den Alliierten eingesetzt (vgl. Hodges, S. 298–299). Anfang bis Mitte der 1950er-Jahre reduzierten Hao Wang und Marvin Minsky die Turingmaschine auf eine einfachere Form (ein Vorläufer der Post-Turing-Maschine von Martin Davis ). Gleichzeitig reduzierten europäische Forscher den neuartigen elektronischen Computer auf ein computerähnliches theoretisches Objekt, das dem entsprach, was heute als „Turingmaschine“ bezeichnet wird. In den späten 1950er und frühen 1960er Jahren führten die zufällig parallel verlaufenden Entwicklungen von Melzak und Lambek (1961), Minsky (1961) sowie Shepherdson und Sturgis (1961) die europäischen Arbeiten weiter und reduzierten die Turingmaschine zu einem benutzerfreundlicheren, computerähnlichen abstrakten Modell, der sogenannten Zählermaschine . Elgot und Robinson (1964), Hartmanis (1971) sowie Cook und Reckhow (1973) führten diese Arbeiten mit den Modellen der Registermaschine und der Random-Access-Maschine noch weiter – im Grunde sind aber alle Mehrband-Turingmaschinen mit einem arithmetikähnlichen Befehlssatz.

Auch heute noch sind Zähler-, Register- und Direktzugriffsmaschinen sowie ihre Vorläuferin, die Turingmaschine, die bevorzugten Modelle für Theoretiker, die Fragen der Berechenbarkeitstheorie untersuchen . Insbesondere die Komplexitätstheorie nutzt die Turingmaschine:

Je nachdem, mit welchen Objekten man in den Berechnungen arbeiten möchte (Zahlen wie nichtnegative ganze Zahlen oder alphanumerische Zeichenketten), haben zwei Modelle in der maschinenbasierten Komplexitätstheorie eine dominante Stellung erlangt:

die Offline-Mehrband-Turingmaschine ..., die das Standardmodell für stringorientierte Berechnungen darstellt, und die Random Access Machine (RAM), wie sie von Cook und Reckhow eingeführt wurde ..., die den idealisierten Von-Neumann-Computer modelliert.

Lediglich im verwandten Bereich der Algorithmenanalyse wird diese Rolle vom RAM-Modell übernommen.