Was ist eine Turing Maschine?

13. Mai 2021 Ralf Hersel Lesezeit: 6 Minuten

Alan Turing erfand 1936 den perfekten Computer.

Die Turingmaschine ist ein klassisches Konzept, das noch vor der Computer-Ära entstanden ist. Dabei handelte es sich um ein logisches Rechenkonstrukt und nicht um einen echten Computer. Das Modell beschreibt, wie ein Rechner eine formalisierte Aufgabe löst, um zum Ergebnis zu gelangen, und welche Anforderungen an den Algorithmus gestellt werden, damit die Maschine die Aufgabe versteht und korrekt ausführt.

Der britische Mathematiker Alan Turing hat 1936 ein abstraktes universelles Modell vorgeschlagen, um das Konzept eines Algorithmus anschaulich zu machen und die Möglichkeiten von Algorithmen mithilfe dieses Modells theoretisch zu erforschen. Dabei handelte es sich um ein logisches Rechenkonstrukt und nicht um eine echte physikalische Rechenmaschine. Obwohl es damals noch keine Computer gab, beschreibt das Modell, wie ein Rechner eine formalisierte Aufgabe löst, um zum Ergebnis zu gelangen, und welche Anforderungen an den Algorithmus gestellt werden, damit die Maschine die Aufgabe versteht und korrekt ausführt.

Das von Turing erfundene theoretische Modell eines Rechners wurde Turingmaschine genannt. Turing wollte sein Modell dazu verwenden, um entweder die Existenz oder die Unmöglichkeit der Existenz eines Algorithmus für eine bestimmte Aufgabe nachzuweisen. Die klassische Turingmaschine ist ein extrem vereinfachtes Modell, das sich jedoch beliebig erweitern und "aufrüsten" lässt, um komplexere Aufgaben zu formalisieren, zu visualisieren und zu beschreiben. Auch Operationen, die von modernen realen Computern ausgeführt werden oder in Netzwerkprotokollen realisiert sind, kann man in einer Turingmaschine nachbilden.

Die klassische Turingmaschine besteht aus einem beidseitig in Zellen unterteilten Endlosband (als Datenspeicher mit Lese- und Schreibzugriff für die aktuelle Zelle) und einem Automaten, der nach den vordefinierten Regeln gesteuert wird. Entsprechend den Daten (dem Zeichen) der aktuell gelesenen Zelle und dem aktuellen Zustand führt die Turingmaschine bestimmte Aktionen aus, die in den Regeln definiert sind. Die Regeln sind in Form einer Tabelle spezifiziert und bilden wie in einem echten Computer das eigentliche Programm, nach dem die Turingmaschine arbeitet, wenn sie eine Aufgabe löst. Für alle zulässigen Daten, die als Buchstaben des externen Alphabets vom Band ausgelesen werden können, und für alle möglichen Zustände des Automaten definiert die Tabelle die entsprechenden Aktionen.

Zu möglichen Aktionen gehören der Übergang zum neuen internen Zustand des Automaten, das Überschreiben der Daten in der aktuellen Zelle sowie die Bewegung des Lese-/Schreibkopfes zur nächstliegenden (rechten oder linken) Zelle auf dem Datenband. Die in der Tabelle definierten Regeln sind die eigentlichen Befehle für die Turingmaschine bei der Lösung der konkreten Aufgabe. Die Daten auf dem Band und die Regeln in der Tabelle sind voneinander genauso unabhängig wie externe Daten vom Algorithmus. Eine in der Tabelle definierte Regel wird anhand der ausgelesenen Daten und des aktuellen Zustands bestimmt und resultiert eine Aktion. Die Daten auf dem Band sind etwa externe Ereignisse, die die Turingmaschine entsprechend den in der Tabelle festgelegten Regeln bearbeitet, um die passenden Aktionen in der Tabelle zu finden und anzuwenden.

Eine Turingmaschine kann das Zeichen der aktuellen Zelle auslesen oder auch überschreiben, den Lese-/Schreibkopf zur nächstliegenden entweder linken oder rechten Zelle des Datenbandes positionieren und den internen Zustand entsprechend den ausgelesenen Daten ändern. Alle möglichen Kombinationen der internen Zustände und der zulässigen externen Daten sind als Regeln in der Tabelle definiert und bestimmen, welches Zeichen in die aktuelle Zelle geschrieben werden soll, in welche Richtung (nach links oder rechts) sich der Kopf bewegen soll und in welchen Zustand der Automat übergeht. Zu möglichen Aktionen gehören auch solche, die den Kopf nicht zur nächsten Zelle bewegen, die Daten der aktuellen Zelle nicht überschreiben oder den aktuellen Zustand nicht ändern.

Beispiel einer Turingmaschine

Angenommen, auf dem Band befindet sich ein Wort, das aus den Zeichen A, B, 1 und 0 besteht, zum Beispiel, 1A0B10. Die Aufgabe ist es, alle Zeichen A und B durch Nullen zu ersetzen. Zum Zeitpunkt des Starts befindet sich der Kopf links über dem ersten Buchstaben des Wortes. Das Programm endet, wenn sich der Kopf über dem leeren Zeichen (einem Trennzeichen) nach dem letzten Buchstaben des Wortes befindet.

Die Regeln in der Tabelle werden wie folgt definiert:

Wenn das aktuelle Zeichen 0 ist, dann den Kopf nach rechts bewegen (0/->)
Wenn das aktuelle Zeichen 1 ist, dann den Kopf nach rechts bewegen (1/->)
Wenn das aktuelle Zeichen A ist, dann das Zeichen in 0 ändern und den Kopf nach rechts bewegen (A/0,->)
Wenn das aktuelle Zeichen B ist, dann das Zeichen in 0 ändern und den Kopf nach rechts bewegen (B/0,->)

Schrittweise Ausführung des Programms bei Bearbeitung der Buchstaben nacheinander, von links nach rechts: