Eine Turingmaschine ist ein mathematisches Modell der theoretischen Informatik, das eine abstrakte Maschine definiert. Bei diesem Rechnermodell werden nach festgelegten Regeln Manipulationen von Zeichen vorgenommen. Die Turingmaschine ist benannt nach dem britischen Mathematiker Alan Turing, der sie 1936/37 einführte.

Turingmaschinen machen die Begriffe des Algorithmus und der Berechenbarkeit mathematisch fassbar, das heißt, sie formalisieren diese Begriffe. Im Gegensatz zu einem physischen Computer ist eine Turingmaschine damit ein mathematisches Objekt und kann mit mathematischen Methoden untersucht werden.

Eine Turingmaschine repräsentiert einen Algorithmus bzw. ein Programm. Eine Berechnung besteht dabei aus schrittweisen Manipulationen von Symbolen bzw. Zeichen, die nach bestimmten Regeln auf ein Speicherband geschrieben und auch von dort gelesen werden. Ketten dieser Symbole können verschieden interpretiert werden, unter anderem als Zahlen. Damit beschreibt eine Turingmaschine eine Funktion, welche Zeichenketten, die anfangs auf dem Band stehen, auf Zeichenketten, die nach „Bearbeitung“ durch die Maschine auf dem Band stehen, abbildet. Eine Funktion, die anhand einer Turingmaschine berechnet werden kann, wird Turing-berechenbar oder auch einfach berechenbar genannt.

Turingmaschinen spielen auch eine bedeutende Rolle bei der Akzeptanz von formalen Sprachen. So entsprechen die Sprachen, die von Turingmaschinen akzeptiert werden, den mit Typ-0-Grammatiken definierbaren Sprachen. Eine Sprache oder ein Computersystem heißen Turing-vollständig, wenn es alle Operationen ausführen kann, die eine universelle Turingmaschine ausführen kann.

Informelle Beschreibung

Die Turingmaschine hat ein Steuerwerk, in dem sich das Programm befindet, und besteht außerdem aus

• einem unendlich langen Speicherband mit unendlich vielen sequentiell angeordneten Feldern. Pro Feld kann genau ein Zeichen aus einem vordefinierten Alphabet gespeichert werden. Als zusätzliches Zeichen ist ein Blank (englisch für „leer/unbeschrieben“) zugelassen, das einem leeren Feld auf dem Speicherband entspricht.
• einem programmgesteuerten Lese- und Schreibkopf, der sich auf dem Speicherband feldweise bewegen und die Zeichen verändern (im Fall eines zu ‚schreibenden‘ Blanks auch löschen) kann.

Eine Berechnung für ein Eingabewort startet mit dem Eingabewort auf dem Band und dem Lese- und Schreibkopf auf dem ersten Symbol des Eingabeworts. Die Turingmaschine verarbeitet dann die Eingabe auf dem Band schrittweise nach dem festgelegten Programm.

Mit jedem Schritt liest der Lese-Schreib-Kopf das aktuelle Zeichen, überschreibt dieses mit einem anderen (oder dem gleichen) Zeichen und bewegt sich dann ein Feld nach links oder rechts oder bleibt stehen. Welches Zeichen geschrieben wird und welche Bewegung ausgeführt wird, hängt von dem an der aktuellen Position vorgefundenen Zeichen sowie dem Zustand ab, in dem sich die Turingmaschine gerade befindet. Dies wird durch eine zu der Turingmaschine gehörende Überführungsfunktion definiert. Zu Beginn befindet sich die Turingmaschine in einem vorgegebenen Startzustand und geht bei jedem Schritt in einen neuen Zustand über. Die Anzahl der Zustände, in denen sich die Turingmaschine befinden kann, ist endlich. Ein Zustand kann mehrere Male durchlaufen werden, er sagt nichts über die auf dem Band vorliegenden Zeichen aus.

Eine Turingmaschine stoppt, wenn für den aktuellen Zustand und das gelesene Bandsymbol keine Überführung zu einem neuen Zustand definiert ist. Es hängt also im Allgemeinen von der Kombination aus Zustand und Symbol ab, ob die Turingmaschine weiter rechnet oder stoppt. Zustände, in denen die Turingmaschine unabhängig von dem gelesenen Bandsymbol anhält, bezeichnet man als Endzustände. Es gibt aber auch Turingmaschinen, die für gewisse Eingaben niemals stoppen.

Neben der Berechnung von Funktionen wird die Turingmaschine – wie viele andere Automaten – auch für Entscheidungsprobleme eingesetzt, also für Fragen, die mit „ja“ oder „nein“ zu beantworten sind. Bestimmte Endzustände werden als „akzeptierend“, andere als „nicht akzeptierend“ definiert. Die Eingabe wird genau dann akzeptiert, wenn die Turingmaschine in einem akzeptierenden Endzustand endet.

Bedeutung

Der Mathematiker Alan Turing stellte die Turingmaschine 1936 im Rahmen des von David Hilbert im Jahr 1920 formulierten Hilbertprogramms speziell zur Lösung des so genannten Entscheidungsproblems in der Schrift On Computable Numbers, with an Application to the Entscheidungsproblem vor.

Das von Hilbert aufgestellte Entscheidungsproblem fragt, ob eine gegebene Formel der Prädikatenlogik allgemeingültig ist, also ob die Formel unter jeder Interpretation wahr ist. Hilbert stellte die Frage, ob dieses Problem automatisch gelöst werden kann. Die Methode, die für eine prädikatenlogische Formel bestimmt, ob sie allgemeingültig ist, soll also von einer „Maschine“ durchgeführt werden können. Vor der Erfindung des Computers bedeutete dies, dass ein Mensch nach festen Regeln – einem Algorithmus – eine Berechnung durchführt.

Turing definierte mit seinem Modell die Begriffe des Algorithmus und der Berechenbarkeit als formale, mathematische Begriffe. Im Allgemeinen wird davon ausgegangen, dass die Turing-Berechenbarkeit das intuitive Verständnis von Berechenbarkeit trifft, diese Aussage ist als Church-Turing-These bekannt. Ihr wohnt eine starke Plausibilität inne, u. a. durch die mathematische Äquivalenz des Begriffs der Turing-Berechenbarkeit mit anderen Berechenbarkeits-Begriffen (wie zum Beispiel der Ausdrückbarkeit im Lambda-Kalkül oder als partiell-rekursive Funktion, sowie die Berechenbarkeit durch Registermaschinen, welche strukturell heute verwendeten Computern nachempfunden sind). Das Besondere an einer Turingmaschine ist dabei ihre strukturelle Einfachheit. Sie benötigt nur drei Operationen (Lesen, Schreiben und Schreib-Lese-Kopf bewegen), um alle Operationen der üblichen Computerprogramme zu simulieren. Im Rahmen der theoretischen Informatik eignet sie sich deshalb besonders gut zum Beweis von Eigenschaften formaler Probleme, wie sie von der Komplexitäts- und Berechenbarkeitstheorie betrachtet werden.

Die Komplexität (etwa Laufzeit- und Speicherkomplexität) von Algorithmen wird in Bezug auf bestimmte Maschinenmodelle definiert. Auf Turingmaschinen ist etwa die asymptotische Anzahl der Zustandsübergänge in Abhängigkeit von der Eingabelänge ein mögliches Laufzeitkomplexitätsmaß eines Algorithmus. Auf anderen Modellen werden oftmals Komplexitätsmaße definiert, die einen wahlfreien Zugriff auf jede Speicherzelle oder die Ausführung arithmetischer Operationen als einzelne Schritte definieren. Diese Maße eignen sich im beschränkten Rahmen (kleiner Datenmengen bzw. kleiner Zahlen) besonders gut, um die Laufzeit vieler Algorithmen auf realen Computern abzuschätzen und sind dementsprechend oft (insbesondere unspezifiziert) anzutreffen. Auf Grund der sequentiellen Struktur von Turingmaschinen ist daher die Laufzeitkomplexität im Sinne der asymptotischen Anzahl der Zustandsübergänge für viele Algorithmen verglichen mit Definitionen für Registermaschinen höher. Die Komplexitätstheorie befasst sich mit der Frage, für welche Probleme Algorithmen mit welcher Komplexität existieren, etwa in welchen Komplexitätsklassen Probleme liegen bzw. nicht liegen. Sofern es bei der Untersuchung der Laufzeitkomplexität nicht auf Faktoren polynomiell in der Eingabelänge ankommt, sind Turingmaschinen hier recht allgemein einsetzbar, da die Simulation vieler Registermaschinen in vielen Komplexitätsmaßen nur polynomiellen Mehraufwand bedeutet.

Nicht alle mathematischen Funktionen können von einer Turingmaschine berechnet werden, selbst wenn man sich auf wohldefinierte Funktionen mit endlicher Ein- und Ausgabe beschränkt (etwa lassen sich Funktionen zwischen beliebigen reellen Zahlen nicht durch Funktionen mit endlicher Ein- und Ausgabe repräsentieren, da die reellen Zahlen überabzählbar sind, und es gibt formal gesehen Funktionen, die sich überhaupt nicht spezifizieren lassen). So konnte Turing zeigen, dass eine Turingmaschine das Hilbertsche Entscheidungsproblem nicht lösen kann, genau so wenig wie das Halteproblem.

Ebenfalls unentscheidbar ist nach dem Satz von Rice jedwede nicht-triviale Eigenschaft eines Programms in einer turingmächtigen Programmiersprache. Selbst wenn man sich auf terminierende Turingmaschinen beschränkt, ist es unentscheidbar, ob zwei terminierende Turingmaschinen dieselbe Sprache akzeptieren. Die Berechenbarkeitstheorie beschäftigt sich mit der Frage, welche Probleme von welchen Maschinenmodellen berechenbar bzw. nicht berechenbar sind.

Systeme, Computer und Programmiersprachen, die unter Ausblendung der Beschränktheit des Speichers und damit verbundener Eigenschaften eine Turingmaschine emulieren könnten, werden als turingvollständig bezeichnet.

Formale Definition

Formal kann eine deterministische Turingmaschine als 7-Tupel ${\displaystyle M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},\square ,F)}$ dargestellt werden (siehe auch nichtdeterministische Turingmaschine).

• ${\displaystyle Q}$ ist die endliche Zustandsmenge
• ${\displaystyle \Sigma }$ ist das endliche Eingabealphabet
• ${\displaystyle \Gamma }$ ist das endliche Bandalphabet und es gilt ${\displaystyle \Sigma \subset \Gamma }$
• ${\displaystyle \delta \colon (Q\setminus F)\times \Gamma \to Q\times \Gamma \times \{L,N,R\}}$ ist die (partielle) Überführungsfunktion
• ${\displaystyle q_{0}\in Q}$ ist der Anfangszustand
• ${\displaystyle \square \in \Gamma \setminus \Sigma }$ steht für das leere Feld (Blank)
• ${\displaystyle F\subseteq Q}$ die Menge der akzeptierenden Endzustände

Die partielle Überführungsfunktion ${\displaystyle \delta }$ liefert zu einem Zustand und einem gelesenen Bandsymbol (i) den nächsten Zustand, (ii) ein Bandsymbol das in das aktuelle Feld geschrieben wird, und (iii) die Bewegungsrichtung des Lese-Schreib-Kopf (L .. ein Feld nach links, N .. nicht bewegen, R .. ein Feld nach rechts). Da in akzeptierenden Endzuständen die Berechnung auf jeden Fall anhält, sind diese in der Definitionsmenge der Überführungsfunktion ausgenommen.

Konfigurationen

Die Konfiguration einer Turingmaschine beschreibt nicht nur den ihr eigenen momentanen Zustand ${\displaystyle q\in Q}$, sondern auch die Position des Lese-Schreib-Kopfes und die gerade auf dem Band vorhandenen Symbole. Die Symbole befinden sich in einem endlichen Bereich des Bandes, der von unendlich vielen leeren Symbolen umgeben ist. Es genügt deshalb, diesen endlichen Bereich zu betrachten.

Formal besteht eine Konfiguration aus dem aktuellen Zustand ${\displaystyle q\in Q}$, einem endlichen Wort ${\displaystyle u\in \Gamma ^{*}}$, das den Inhalt des Bands links des Lese-Schreib-Kopfes enthält und einem endlichen Wort ${\displaystyle v\in \Gamma ^{*}}$, das den Inhalt des Bandes ab der aktuellen Position des Lese-Schreib-Kopfes enthält. Eine Konfiguration ist also ein Tripel ${\displaystyle (q,u,v)}$ mit ${\displaystyle q\in Q}$, ${\displaystyle u\in \Gamma ^{*}}$, ${\displaystyle v\in \Gamma ^{*}}$, wobei das Band durch ${\displaystyle uv}$ gegeben ist und der Lese-Schreib-Kopf auf dem ersten Zeichen von ${\displaystyle v}$ steht.

Oft werden Konfiguration auch durch eine Folge ${\displaystyle X_{1}X_{2}\cdots X_{i-1}qX_{i}X_{i+1}\cdots X_{n}}$, mit ${\displaystyle X_{\ell }\in \Gamma ,q\in Q}$ beschrieben, bei der der aktuelle Zustand ${\displaystyle q}$ an der aktuellen Position des Lese-Schreibkopfes in das Wort, das den Bandinhalt wiedergibt, eingefügt wird. ${\displaystyle X_{1}}$ ist das am weitesten links stehende, nicht-leere Bandsymbol, ${\displaystyle X_{n}}$ das am weitesten rechts stehende, nicht-leere Bandsymbol, und ${\displaystyle X_{i}}$ das Symbol über dem sich der Lese-Schreibkopf befindet. Bewegt sich der Lese-Schreib-Kopf über den Rand hinaus, sind der Konfiguration noch weitere ${\displaystyle \square }$-Symbole hinzuzufügen.

Durch eine Startkonfiguration wird das Eingabewort festgelegt. Eine übliche Startkonfiguration ist ${\displaystyle q_{0}X_{1}\cdots X_{n}}$ mit Startzustand ${\displaystyle q_{0}}$ und Eingabewort ${\displaystyle X_{1}\cdots X_{n}}$. Diese entspricht dem Tripel ${\displaystyle (q_{0},\epsilon ,X_{1}\cdots X_{n})}$, wobei ${\displaystyle \epsilon }$ das leere Wort ist.

Beispiel

Die folgende deterministische Ein-Band-Turingmaschine ${\displaystyle M}$ erwartet eine Folge von Einsen als Eingabe auf dem Band. Sie verdoppelt die Anzahl der Einsen, wobei ein Leersymbol in der Mitte stehen bleibt. Aus „11“ wird beispielsweise die Zeichenfolge „11011“. Der Schreib-/Lesekopf befindet sich initial auf der ersten Eins. Der Anfangszustand ist ${\displaystyle s1}$, der Endzustand ${\displaystyle s6}$. Die Null steht für das leere Feld ${\displaystyle \square }$ und das Band besteht bis auf die darauf geschriebenen Einsen aus leeren Feldern.

${\displaystyle M=(Q,\Sigma ,\Gamma ,\delta ,s1,0,\{s6\})}$

• ${\displaystyle Q=\{s1,s2,s3,s4,s5,s6\}}$
• ${\displaystyle \Sigma =\{1\}}$
• ${\displaystyle \Gamma =\{1,0\}}$

Die Überführungsfunktion ${\displaystyle \delta }$ ist wie folgt definiert:

${\displaystyle M}$ durchläuft im oben erwähnten Beispiel, also bei der Eingabe „11“, folgende Zustände, wobei die aktuelle Kopfposition fett gedruckt ist:

Die Berechnung beginnt im Anfangszustand ${\displaystyle s1}$. Hier wird die erste Eins durch ein leeres Feld ersetzt, der Schreib-Lese-Kopf bewegt sich nach rechts und neuer Zustand wird ${\displaystyle s2}$. Der Kopf wandert nun solange nach rechts, bis ein leeres Feld gelesen wird. Danach gelangt die Turingmaschine in den Zustand ${\displaystyle s3}$ und überliest alle weiteren Einsen, bis sie erneut ein leeres Feld findet. Dieses wird dann durch eine Eins ersetzt. Im Zustand ${\displaystyle s4}$ bewegt sich der Kopf zurück, überliest wieder alle Einsen, bis er auf ein leeres Feld trifft, Zustandswechsel auf ${\displaystyle s5}$. Der Kopf bewegt sich nun solange nach links, bis das ursprünglich in Zustand ${\displaystyle s1}$ geschriebene leere Feld gefunden wird. Dieses wird wieder durch eine Eins ersetzt, der Kopf bewegt sich ein Feld nach rechts und die Turingmaschine gelangt wieder in den Zustand ${\displaystyle s1}$. Hier beginnt ein neuer Rechenzyklus.
Wird im Zustand ${\displaystyle s1}$ ein leeres Feld gelesen, so gelangt die Turingmaschine ${\displaystyle M}$ in den Endzustand ${\displaystyle s6}$, woraufhin die Berechnung beendet wird.

Äquivalente Varianten der Turingmaschine

In der Literatur findet man zahlreiche unterschiedliche Definitionen und Varianten der Turingmaschine, die sich jeweils in einigen Details unterscheiden. Diese sind äquivalent in dem Sinne, dass Turingmaschinen einer Definition leicht in Turingmaschinen der anderen Definitionen umgewandelt werden können, sodass diese die gleichen Berechnungen durchführen. Häufige Abweichungen von der obigen Definition sind:

• Es wird nicht zwischen Eingabealphabet und Bandalphabet unterschieden.
• Statt einer Menge von akzeptierenden Endzuständen gibt es nur einen einzigen akzeptierenden Endzustand.
• Zusätzlich zu einem oder mehreren akzeptierenden Endzuständen gibt es noch einen oder mehrere verwerfende Endzustände.^[1]
• Der Lese-Schreib-Kopf bewegt sich immer entweder nach links oder nach rechts. Für die Bewegung des Kopfes gibt es also nur die Symbole ${\displaystyle L,R}$.^[2]
• Die Funktion ${\displaystyle \delta }$ ist als totale Funktion gegeben. Die Maschine hält in Endzuständen und in Zuständen ${\displaystyle q\in Q}$, wenn das Symbol ${\displaystyle a}$ gelesen wird und ${\displaystyle \delta (q,a)=(q,a,N)}$.^[3]
• Semiunendliches Speicherband: Das Speicherband ist nur in eine Richtung unendlich. Es gibt ein spezielles Symbol, das den Anfang der Eingabe markiert. Der Lese-/Schreibkopf kann sich dann nicht darüber hinaus nach links bewegen, aber beliebig weit nach rechts.^[1]

Zudem gibt es Erweiterungen, die ebenfalls hinsichtlich der Berechenbarkeit äquivalent zu Turingmaschinen sind. Selbst komplexitätstheoretisch sind die Unterschiede zwischen vielen der Varianten weitgehend zu vernachlässigen. Insgesamt führen sehr viele Varianten zu nicht mehr als polynomialen Aufwandsunterschieden (wobei Aufwand hier eine beliebige Ressource meint) und sind daher für viele komplexitätstheoretische Untersuchungen vernachlässigbar. Man passt in Abhängigkeit von den Zielen der jeweiligen Analyse das verwendete Modell so an, dass die Analyse möglichst einfach durchgeführt werden kann. Es gibt jedoch auch hinsichtlich der Berechenbarkeit, nicht aber der Komplexität (im Sinne von „bis auf polynomiellen Mehraufwand“), äquivalente Erweiterungen der Turingmaschine, wie zum Beispiel nichtdeterministische Turingmaschinen und bestimmte Orakel-Turingmaschinen.

• Mehrspuren-Turingmaschine (engl. Multi-track Turing machine): Turingmaschinen, die erlauben, mehrere Symbole in ein Feld des Speicherbands zu speichern.
• Mehrband-Turingmaschine (engl. Multitape Turing machine): Turingmaschinen mit mehreren Bändern mit jeweils einem Lese-Schreib-Kopf.
• Vergessliche Turingmaschine (engl. Oblivious Turing machines): Eine Turingmaschine wird vergesslich^[4] oder auch bewegungsuniform^[5] genannt, falls die Kopfbewegungen nicht vom konkreten Inhalt der Eingabe abhängen, sondern nur von der Länge der Eingabe. Jede Turingmaschine kann durch eine vergessliche simuliert werden.^[6]
• Zweikellerautomat (engl. Two-stack Push Down Automaton): Ein Kellerautomat mit zwei Kellerspeichern.
• Zählermaschinen (engl. Counter Machine)^[7] mit mindestens 2 Zählern.

Universelle Turingmaschine

In der obigen Definition ist das Programm fest in die Maschine eingebaut und kann nicht verändert werden. Kodiert man die Beschreibung einer Turingmaschine als hinreichend einfache Zeichenkette, so kann man eine sogenannte universelle Turingmaschine – selbst eine Turingmaschine – konstruieren, welche eine solche Kodierung einer beliebigen Turingmaschine als Teil ihrer Eingabe nimmt und das Verhalten der kodierten Turingmaschine auf der ebenfalls gegebenen Eingabe simuliert. Aus der Existenz einer solchen universellen Turingmaschine folgt zum Beispiel die Unentscheidbarkeit des Halteproblems. Eine ähnliche Idee, bei der das Programm als ein Teil der veränderbaren Eingabedaten betrachtet wird, liegt auch fast allen heutigen Rechnerarchitekturen zugrunde (Von-Neumann-Architektur).

Formal ist eine universelle Turingmaschine eine Maschine ${\displaystyle {\mathit {UTM}}_{\phi }}$, die eine Eingabe ${\displaystyle w\|x}$ liest. Das Wort ${\displaystyle w}$ ist hierbei eine hinreichend einfache Beschreibung einer Maschine ${\displaystyle M_{w}}$, die zu einer bestimmten Funktion mit Eingabe ${\displaystyle x}$ die Ausgabe berechnet. ${\displaystyle \|}$ ist ein Trennzeichen zwischen Programmbeschreibung und Eingabe. ${\displaystyle {\mathit {UTM}}_{\phi }}$ simuliert also das Verhalten von ${\displaystyle M_{w}}$ mit Hilfe der Funktionsbeschreibung ${\displaystyle w}$ und der Eingabe ${\displaystyle x}$. Der Index ${\displaystyle \phi }$ in ${\displaystyle {\mathit {UTM}}_{\phi }}$ zeigt an, dass es nicht nur eine einzige universelle Turingmaschine gibt. So könnten z. B. ${\displaystyle {\mathit {UTM}}_{1}}$ und ${\displaystyle {\mathit {UTM}}_{2}}$ verschiedene Wörter verstehen. Das Wort ${\displaystyle w}$ muss dabei in einer Sprache codiert sein, die die ${\displaystyle {\mathit {UTM}}_{\phi }}$ versteht.

Bekannte Turingmaschinen

Fleißiger Biber

Als Fleißige Biber (engl. Busy Beaver) werden die deterministischen Turingmaschinen bezeichnet, die bezogen auf alle terminierenden, deterministischen Turingmaschinen mit derselben Anzahl von Zuständen und Symbolen die maximale Anzahl eines bestimmten Symbols auf das Band schreiben und dann anhalten. Es existiert keine berechenbare Funktion, die einer gegebenen Anzahl von Symbolen und Zuständen eines entsprechenden Fleißigen Bibers, die Anzahl der von ihm am Ende geschriebenen Symbole (die sogenannte Radó-Funktion) oder die Anzahl der Schritte zuordnet, die er braucht, um zu terminieren.

An Turingmaschinen angelehnte Maschinenmodelle

Beziehung zwischen einer Turingmaschine und einer formalen Sprache

Literatur

• Rolf Herken (Hrsg.): The Universal Turing Machine. A Half-Century Survey (= Computerkultur. Band 2). 2. Auflage. Springer, Wien u. a. 1995, ISBN 3-211-82637-8. 
• Juraj Hromkovič: Theoretische Informatik. Formale Sprachen, Berechenbarkeit, Komplexitätstheorie, Algorithmik, Kommunikation und Kryptographie. 3., überarbeitete und erweiterte Auflage. Teubner, Wiesbaden 2007, ISBN 978-3-8351-0043-5. 
• John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation. 2. Auflage. Addison-Wesley, Boston MA u. a. 2001, ISBN 978-0-201-44124-6. 
• Sybille Krämer: Symbolische Maschinen. Die Idee der Formalisierung im geschichtlichen Abriß. Wissenschaftliche Buchgesellschaft, Darmstadt 1988, ISBN 3-534-03207-1.
• Heinz Lüneburg: Rekursive Funktionen. Springer, Berlin u. a. 2002, ISBN 3-540-43094-6. 
• Marvin L. Minsky: Computation. Finite and Infinite Machines. Prentice-Hall, Englewood Cliffs NJ 1967.
• Charles Petzold: The Annotated Turing. A guided Tour through Alan Turing’s historic Paper on Computability and the Turing Machine. John Wiley & Sons, Indianapolis IN 2008, ISBN 978-0-470-22905-7.
• Boris A. Trachtenbrot: Algorithmen und Rechenautomaten. VEB Deutscher Verlag der Wissenschaften Berlin 1977.
• Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem. In: Proceedings of the London Mathematical Society. Band 42, 1937, ISSN 0024-6115, S. 230–265, doi:10.1112/plms/s2-42.1.230 (Oxford Journals). 
• Oswald Wiener, Manuel Bonik, Robert Hödicke: Eine elementare Einführung in die Theorie der Turing-Maschinen. Springer, Wien/New York 1998, ISBN 3-211-82769-2. 

Weblinks

Commons: Turing machines  – Sammlung von Bildern, Videos und Audiodateien

Wiktionary: Turingmaschine  – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen

• David Barker-Plummer: Turing Machines. In: Edward N. Zalta (Hrsg.): Stanford Encyclopedia of Philosophy.
• Georg Weuffen: Die Turing-Maschine. In: MathePrisma Multimedia-Projekt der Bergischen Universität Wuppertal
• Turingmaschinen auf informatikseite.de
• Einband-/Mehrband-Turingmaschine: Simulation der Grundrechenarten (JavaScript)
• Website über eine physikalische Turing-Maschine (inklusive Video)
• elstel.org/coan/ Turingsimulator: ein Programm, das auch nicht-deterministische Turingmaschinen und Maschinenschemata simulieren kann

Einzelnachweise

1. 1 2 Juraj Hromkovič: Theoretische Informatik. Formale Sprachen, Berechenbarkeit, Komplexitätstheorie, Algorithmik, Kommunikation und Kryptographie. 3. Auflage. B.G. Teubner Verlag, Heidelberg 2007, ISBN 978-3-8351-0043-5. 
2. ↑ John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. 3., aktualisierte Auflage. Pearson Studium, München 2011, ISBN 978-3-86894-082-4. 
3. ↑ Ingo Wegener: Theoretische Informatik. Eine algorithmenorientierte Einführung. B.G. Teubner, Stuttgart, ISBN 3-519-02123-4. 
4. ↑ auf englisch: oblivious, siehe Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach. Cambridge University Press, Cambridge / New York 2009, ISBN 978-0-521-42426-4, S. 45 (princeton.edu [PDF; abgerufen am 13. Juni 2013]). 
5. ↑ Karl Rüdiger Reischuk: Komplexitätstheorie. 2. Auflage. Band I: Grundlagen. Teubner, 1999, ISBN 978-3-519-12275-3, S. 103. 
6. ↑ Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach. Cambridge University Press, Cambridge / New York 2009, ISBN 978-0-521-42426-4, S. 19 (princeton.edu [PDF; abgerufen am 13. Juni 2013] Remark 1.10). 
7. ↑ John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. 3., aktualisierte Auflage. Pearson Studium, München 2011, ISBN 978-3-86894-082-4, 8.5.3 Zählermaschinen 8.5.4 Die Leistungsfähigkeit von Zählermaschinen. 
8. ↑ Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem. November 1936, S. 8–10. 
9. ↑ Eintrag zur probabilistischen Turingmaschine auf der Seite des NIST
10. ↑ Goldin et al., 2003: Turing Machines, Transition Systems and Interaction