Turingmaschine: Aufbau, Ablauf und Grenzen

Eine Turingmaschine ist ein mathematisches Modell der theoretischen Informatik. Sie definiert eine abstrakte Maschine, also keinen echten Computer. Benannt ist sie nach dem britischen Mathematiker Alan Turing, der sie 1936/37 einführte.

Die Maschine hat drei Hauptteile. Das Speicherband ist unendlich lang und hat unendlich viele Felder, die der Reihe nach angeordnet sind. Jedes Feld speichert genau ein Zeichen aus einem festgelegten Alphabet. Der Lese- und Schreibkopf wird vom Programm gesteuert. Er bewegt sich feldweise auf dem Band und kann die Zeichen verändern. Das Steuerwerk enthält das Programm.

Die Überführungsfunktion legt fest, welches Zeichen geschrieben wird und welche Bewegung ausgeführt wird. Beides hängt vom gelesenen Zeichen und vom aktuellen Zustand ab. Die Maschine startet in einem vorgegebenen Startzustand, und die Anzahl ihrer Zustände ist endlich. Ein Zustand sagt nichts über die Zeichen auf dem Band aus.

Die Überführungsfunktion nimmt als Argument den aktuellen Zustand und das Zeichen unter dem Lese- und Schreibkopf. Eine Regel liest du so: Zustand, gelesenes Zeichen → geschriebenes Zeichen, neuer Zustand, Bewegung. Das Feld unter dem Kopf wird mit dem gelieferten Zeichen überschrieben. Bei der Bewegung L geht der Kopf ein Feld nach links, bei R ein Feld nach rechts, und bei N bleibt er auf demselben Feld.

Als Beispiel dient eine Maschine, die eine Folge von Einsen erwartet und deren Anzahl verdoppelt. Dabei bleibt ein Leersymbol in der Mitte stehen: Aus „11“ wird „11011“. Der Kopf steht anfangs auf der ersten Eins, der Anfangszustand ist s1 und der Endzustand ist s6. Die 0 steht für das leere Feld. Der Rest des Bandes besteht aus leeren Feldern.

So simulierst du: Notiere Zustand, Band und Kopfposition. Suche die Regel zu Zustand und gelesenem Zeichen. Überschreibe das Feld, bewege den Kopf und notiere den neuen Zustand. Dann wiederholst du das. Bei der Eingabe „11“ beginnt die Berechnung in Schritt 1 im Zustand s1 mit dem Band 11000 und dem Kopf auf der ersten Eins. In Schritt 2 ist der Zustand s2, das Band 01000 und der Kopf auf der zweiten Stelle. In Schritt 16 ist die Maschine im Zustand s6 und hält.

So arbeitet die Maschine im Überblick: Im Zustand s1 ersetzt sie die erste Eins durch ein leeres Feld, der Kopf geht nach rechts, und der neue Zustand ist s2. Der Kopf wandert dann nach rechts, bis er ein leeres Feld liest. Im Zustand s3 überliest sie alle weiteren Einsen, bis sie ein leeres Feld findet. Dieses ersetzt sie durch eine Eins. Wird im Zustand s1 ein leeres Feld gelesen, gelangt die Maschine in den Endzustand s6, und die Berechnung ist beendet.

Eine Turingmaschine stoppt, wenn für den aktuellen Zustand und das gelesene Bandsymbol keine Überführung zu einem neuen Zustand definiert ist. Zustände, in denen die Maschine unabhängig vom gelesenen Bandsymbol anhält, heißen Endzustände. Erreicht die Maschine einen Endzustand, kann sie keine weiteren Aktionen durchführen, und die Berechnung ist beendet.

Bei Entscheidungsproblemen sind Fragen mit „ja“ oder „nein“ zu beantworten. Dabei gelten bestimmte Endzustände als akzeptierend, andere als nicht akzeptierend. Eine Turingmaschine akzeptiert ein Wort, wenn die Berechnung in der Startkonfiguration beginnt und in einer Konfiguration mit einem akzeptierenden Endzustand endet. Endet die Berechnung in einer anderen Konfiguration, verwirft sie das Eingabewort. Manche Varianten haben zusätzlich verwerfende Endzustände.

Es gibt aber auch Turingmaschinen, die für gewisse Eingaben niemals stoppen. Ihre Berechnung ist dann eine unendliche Folge von Konfigurationsschritten. Ist die Berechnung unendlich, wird das Wort weder akzeptiert noch verworfen.

Noch ein Unterschied: Eine Sprache ist hier eine Menge von Eingabewörtern. Eine Turingmaschine akzeptiert eine Sprache, wenn sie jedes Wort der Sprache nach endlich vielen Schritten in einem akzeptierenden Zustand hält. Bei jedem Wort außerhalb der Sprache hält sie in einem nicht akzeptierenden Zustand oder überhaupt nicht. Hält sie zusätzlich bei allen Eingaben, die nicht zur Sprache gehören, so entscheidet sie diese Sprache.

Bei einer gewöhnlichen Turingmaschine ist das Programm fest eingebaut und kann nicht verändert werden. Man kann aber die Aktionstabelle, also die Übergangsregeln, einer beliebigen Turingmaschine als Zeichenkette kodieren. Eine universelle Turingmaschine (UTM) nimmt eine solche Kodierung als Teil ihrer Eingabe und simuliert das Verhalten der kodierten Maschine auf der ebenfalls gegebenen Eingabe. Sie liest beides von ihrem eigenen Band. Die Eingabe hat die Form w|x. Dabei beschreibt w die zu simulierende Maschine, x ist die Eingabe für diese Maschine, und das Zeichen | ist ein Trennzeichen. Es gibt nicht nur eine einzige UTM.

Was sie leistet: Eine UTM kann jede rekursive Funktion berechnen, jede rekursive Sprache entscheiden und jede rekursiv aufzählbare Sprache akzeptieren. Eine Sprache heißt rekursiv oder entscheidbar genau dann, wenn es eine Turingmaschine gibt, die sie entscheidet. Sie heißt rekursiv aufzählbar, wenn es eine Turingmaschine gibt, die sie akzeptiert. „Entscheiden“ und „akzeptieren“ kennst du aus dem Abschnitt davor. Man geht im Allgemeinen davon aus, dass die Turing-Berechenbarkeit das intuitive Verständnis von Berechenbarkeit trifft. Diese Aussage heißt Church-Turing-These. Nach ihr sind die von einer UTM lösbaren Probleme genau die Probleme, die von einem Algorithmus oder einer effektiven Berechnungsmethode lösbar sind. Ein System, das eine UTM simulieren kann, heißt Turing-vollständig. Eine UTM dient als Standard, mit dem man Rechensysteme vergleichen kann. Eine ähnliche Idee, bei der das Programm Teil der veränderbaren Eingabedaten ist, liegt fast allen heutigen Rechnerarchitekturen zugrunde (Von-Neumann-Architektur).

Wo die Grenzen liegen: Nicht alle mathematischen Funktionen können von einer Turingmaschine berechnet werden. Das Halteproblem kann eine Turingmaschine nicht lösen. Die meisten Fragen über das Verhalten anderer Turingmaschinen sind unentscheidbar. Das heißt, die betreffende Funktion kann nicht mechanisch berechnet werden.