Turing-Maschine

Eine Turing-Maschine besteht aus wenigen Komponenten:

• Band (Tape): Das Band ist wie eine endlose Reihe von Kästchen, die nach links und rechts unbegrenzt weitergehen. In jedem Kästchen steht genau ein Symbol, zum Beispiel „0“ oder „1“.
• Kopf (Head): Der Kopf kann sich auf dem Band nach links oder rechts bewegen. Er liest das Zeichen im aktuellen Kästchen, kann es verändern (überschreiben) und sich dann weiterbewegen.
• interner Zustandsregister: Das Verhalten der Maschine wird durch ihre aktuelle Position auf dem Band, das gelesene Symbol und den aktuellen internen Zustand bestimmt. Es gibt nur eine bestimmte Anzahl an Zuständen. Einer davon ist der Startzustand, und es kann auch ein Endzustand festgelegt sein.
• Übergangsfunktion: Alle Informationen fließen in eine sogenannte Übergangsfunktion ein, die festlegt, was die Maschine als Nächstes tun soll: Welches Symbol geschrieben wird, in welchen Zustand sie wechselt und in welche Richtung sich der Kopf bewegt.

Die Turing-Maschine arbeitet schrittweise: Sie liest ein Symbol vom Band, führt gemäß Übergangsfunktion die entsprechenden Operationen aus, und wiederholt diesen Prozess. Die Maschine startet in einem definierten Anfangszustand und mit einem bestimmten Bandinhalt (der Eingabe). Sie verarbeitet diese Eingabe durch sukzessive Anwendung der Übergangsregeln. Die Berechnung endet entweder, wenn ein spezieller Haltezustand erreicht wird ("Programmende") oder sie läuft unendlich weiter, falls keine Regel mehr passt oder das Problem nicht lösbar ist.

Beispiel

Eine Regel könnte lauten, dass die Maschine im Zustand q₀​, wenn sie das Zeichen "1" liest, dieses in eine "0" umschreibt, sich nach rechts bewegt und in den Zustand q₁​ übergeht. Ein Programm ist also nichts anderes als eine definierte Menge solcher Regeln. Durch ihre Ausführung simuliert die Turing-Maschine schrittweise eine algorithmische Berechnung.

Die Turing-Maschine hat in erster Linie eine theoretische Funktion. In der Informatik dient sie als Fundament der Komplexitäts- und Berechenbarkeitstheorie. Die Turing-Maschine dient als Referenzmodell, um zwei wichtige Klassen von Problemen zu unterscheiden: berechenbare und entscheidbare Probleme.

Ein Problem ist berechenbar, wenn es überhaupt irgendeine Turing-Maschine gibt, die es lösen kann. Ein Problem ist entscheidbar, wenn die zugehörige Turing-Maschine immer zum Ende kommt, egal welche Eingabe man gibt. Das Halteproblem ist das klassische Gegenbeispiel: Es kann keinen Algorithmus geben kann, der für jedes beliebige Programm entscheiden kann, ob es irgendwann anhält oder unendlich weiterläuft. Es ist somit nicht entscheidbar, unabhängig von Rechenleistung oder technischer Umsetzung.

Des Weiteren wird zwischen entscheidbaren und semi-entscheidbaren Problemen unterschieden. Entscheidbar bedeutet, dass es eine Turing-Maschine gibt, die bei jeder Eingabe irgendwann ein eindeutiges "ja" oder "nein" liefert. Semi-entscheidbar bedeutet: Es gibt eine Turing-Maschine, die im Fall von "ja" immer ein Ergebnis liefert, aber im Fall von "nein" eventuell nie anhält. Solche Probleme können also teilweise gelöst werden (z.B. durch systematisches Durchprobieren), aber man weiß nie sicher, ob man das "nein" irgendwann bekommt oder ewig wartet.

Auch wenn die Turing-Maschine ein vollständiges Berechnungsmodell ist, hat sie praktische Einschränkungen. Sie ist extrem langsam, nicht effizient, und die Umsetzung selbst kleinster Operationen erfordert viele Einzelschritte. Sie besitzt keine parallelen Strukturen, keinen Speicher im modernen Sinn und keine pragmatische Bedienbarkeit.

Ein zentrales Konzept ist die sogenannte universelle Turing-Maschine (UTM). Dabei handelt es sich um eine Turing-Maschine, die nicht nur eine feste Aufgabe löst, sondern so konstruiert ist, dass sie beliebige andere Turing-Maschinen simulieren kann. Man gibt ihr die Beschreibung einer anderen Turing-Maschine sowie die passende Eingabe, und die UTM führt dann genau das aus, was dieses Programm tun würde. Damit ist die UTM ein früher theoretischer Vorläufer des allgemein programmierbaren Rechners.

Ein formaler Begriff, der aus der Turing-Theorie hervorgeht, ist die Turing-Vollständigkeit. Ein System ist genau dann Turing-vollständig, wenn es alle Funktionen berechnen kann, die auch eine Turing-Maschine berechnen kann. Solche Systeme sind im Prinzip ebenso mächtig wie das Turing-Modell, auch wenn sie in der Praxis Einschränkungen wie begrenzten Speicher haben. Beispiele für Turing-vollständige Systeme sind fast alle modernen Programmiersprachen (z.B. Python, Java, C).

Die sogenannte Church-Turing-These ist eine zentrale philosophische Annahme der theoretischen Informatik. Sie besagt: "Die Klasse der Turing-berechenbaren Funktionen stimmt mit der Klasse der intuitiv berechenbaren Funktionen überein." Mit anderen Worten: Alles, was man sich als "mechanisch berechenbar“ vorstellen kann – also eine schrittweise, eindeutige Rechenvorschrift – lässt sich auch mit einer Turing-Maschine umsetzen. Die These ist nicht formal beweisbar, weil der Begriff "intuitiv berechenbar" keine mathematisch scharfe Definition besitzt. Bisher wurde kein Gegenbeispiel gefunden; jede formal beschreibbare Berechnung lässt sich bislang als Turing-Maschine darstellen.

Die Turing-Maschine ist nicht nur für Berechenbarkeit zentral, sondern auch für die Komplexitätstheorie. Sie dient als Basis für die Definition von Komplexitätsklassen, d.h. Kategorien, mit denen man Probleme danach einteilt, wie viel Rechenaufwand (Zeit oder Speicher) nötig ist, um sie algorithmisch zu lösen. Man unterscheidet u.a. P ("polynomial time"), NP ("nondeterministic polynomial time"), NP-complete, PSPACE und EXPTIME.

Reale Computer sind keine echten Turing-Maschinen, denn sie haben nur endlichen Speicher, begrenzte Rechenzeit und sind fehleranfällig. Trotzdem gelten sie in der Praxis als Turing-äquivalent, weil sie alle berechenbaren Probleme lösen können, solange ausreichend Ressourcen vorhanden sind. Eine reale CPU kann also wie eine Turing-Maschine arbeiten, nur eben auf physikalisch begrenztem Niveau.