Was ist eine Turingmaschine?

Von der Turingmaschine zum Quantencomputer

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 eine 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 mit Hilfe 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 Turingmaschine ist ein klassisches Konzept, das noch vor der Computer-Ära entstanden ist. Du kannst dir eine Turingmaschine am besten vorstellen und dich mit diesem Konzept vertraut machen, indem Du die Begriffe, die Alan Turing ursprünglich bei Beschreibung seiner Maschine verwendet hatte, in gebräuliche Begriffe der modernen Informationstechnik wie beispielsweise externe Daten, Lese- und Schreibzugriffe, Zustände, Befehle und Aktionen übersetzt. Solche modernen Begriffe werden wir hier verwenden, weil sie die Grundbegriffe der Informatik sind und die Arbeitsweise einer Turingmaschine verständlich machen.

Was ist eine Turingmaschine?

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 der Tabelle definierten Regeln sind die eigentlichen Befehle für die Turing-Maschine 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.

Damit Du eine Turingmaschine zur Lösung einer bestimmten Aufgabe verwenden kannst, musst Du die folgenden Komponenten beschrieben:

• Externes Alphabet – eine endliche Menge, deren Elemente Buchstaben (Zeichen) genannt werden. Einer der Buchstaben dieses Alphabets muss ein leeres Zeichen beziehungsweise ein Trennzeichen sein.
• Internes Alphabet – eine endliche Menge von Zuständen des Automaten. Einer der Zustände (q1) muss initial sein, um das Programm zu starten. Ein anderer der Zustände (q0) muss der Zustand der Unterbrechung sein, um die Ausführung des Programms zu beenden.
• Übergangstabelle – sie beschreibt das Verhalten des Automaten in Abhängigkeit von seinem aktuellen Zustand und dem aktuell gelesenen Zeichen.

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:

1. Zeichen (1): 1A0B10 -> 1A0B10
2. Zeichen (A): 1A0B10 -> 100B10
3. Zeichen (0): 100B10 -> 100B10
4. Zeichen (B): 100B10 -> 100010
5. Zeichen (1): 100010 -> 100010
6. Zeichen (0): 100010 -> 100010
7. Zeichen (Trennzeichen): Ende

Das resultierende Wort am Ende der Programmausführung ist 100010.

Eine weitere sehr anschauliche Erklärung (auf Englisch) zur Turingmaschine findest Du hier:

Fazit

Die Turingmaschine ist eine der faszinierendsten und aufregendsten intellektuellen Entdeckungen des 20. Jahrhunderts. Dies ist ein einfaches und nützliches abstraktes Computermodell, das häufig ausreichend ist, um jede Computeraufgabe zu formalisieren und den gefundenen Algorithmus in einer Programmiersprache zu implementieren. Dank einem einfachen jedoch universellen und erweiterbaren Konzept bildet die Turingmaschine die Grundlage der theoretischen Informatik. Das Konzept führt zu einem tieferen Verständnis sowohl von digitalen Computern als auch von Netzwerkprotokollen und digitaler Kommunikation.

Mit Hilfe der Turingmaschine wurden komplexe wissenschaftliche Rechenprobleme identifiziert, die mit gängigen Computern und traditionellen sequenziellen Algorithmen nicht lösbar sind. Es ist jedoch zu erwarten, dass eine Quanten-Turingmaschine zur Beschreibung von Quantenalgorithmen für Quantencomputer erfunden wird, die das Computing der Zukunft revolutioniert und zu bahnbrechenden Entwicklungen und Technologien führt.