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 abbildet, die nach „Bearbeitung“ durch die Maschine auf dem Band stehen. 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. Es konnte gezeigt werden, dass eine Transformationsgrammatik der Grammatik einer Turingmaschine entsprechen kann, die in der Lage ist, jede berechenbare Funktion zu berechnen.George A. Miller: Wörter. Streifzüge durch die Psycholinguistik. Herausgegeben und aus dem Amerikanischen übersetzt von Joachim Grabowski und Christiane Fellbaum. Spektrum der Wissenschaft, Heidelberg 1993; Lizenzausgabe: Zweitausendeins, Frankfurt am Main 1995; 2. Auflage ebenda 1996, ISBN 3-86150-115-5, S. 255. 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 gerahmt|Ein-Band-Turingmaschine mini|Modell einer Turingmaschine 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 einen akzeptierbaren Endzustand liefert.
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 sei, also ob die Formel unter jeder Interpretation wahr sei. Hilbert stellte die Frage, ob dieses Problem automatisch gelöst werden könne. Die Methode, die für eine prädikatenlogische Formel bestimmt, ob sie allgemeingültig sei, 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. Aufgrund 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 Hilbert’sche Entscheidungsproblem nicht lösen kann, genauso wenig das Halteproblem.
Ebenfalls unentscheidbar ist nach dem Satz von Rice jede 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.
Formalere Definition Formaler kann eine deterministische Turingmaschine als 7-Tupel dargestellt werden (siehe auch nichtdeterministische Turingmaschine):
ist die endliche Zustandsmenge ist das endliche Eingabealphabet ist das endliche Bandalphabet und es gilt ist die (partielle) Überführungsfunktion ist der Anfangszustand steht für das leere Feld (Blank) die Menge der akzeptierenden Endzustände
Die partielle Überführungsfunktion 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-Kopfes (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 mini|Konfiguration einer Turingmaschine im Zustand . Der Lese-Schreibkopf befindet sich über dem grau hervorgehobenen -Symbol. Verwendet man als das Blank-Symbol der Turingmaschine, entspricht diese Konfiguration dem Tripel
Die Konfiguration einer Turingmaschine beschreibt nicht nur den ihr eigenen momentanen Zustand , 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 , einem endlichen Wort , das den Inhalt des Bands links des Lese-Schreib-Kopfes enthält, und einem endlichen Wort , das den Inhalt des Bandes ab der aktuellen Position des Lese-Schreib-Kopfes enthält. Eine Konfiguration ist also ein Tripel mit , , , wobei das Band durch gegeben ist und der Lese-Schreib-Kopf auf dem ersten Zeichen von steht.
Oft werden Konfigurationen auch durch eine Folge , mit , beschrieben, bei der der aktuelle Zustand an der aktuellen Position des Lese-Schreib-Kopfes in das Wort, das den Bandinhalt wiedergibt, eingefügt wird. ist das am weitesten links stehende nicht-leere Bandsymbol, das am weitesten rechts stehende nicht-leere Bandsymbol und das Symbol, über dem sich der Lese-Schreib-Kopf befindet. Bewegt sich der Lese-Schreib-Kopf über den Rand hinaus, sind der Konfiguration noch weitere -Symbole hinzuzufügen.
Durch eine Startkonfiguration wird das Eingabewort festgelegt. Eine übliche Startkonfiguration ist mit Startzustand und Eingabewort .