Präzisierung der Turingmaschine
Was ist eigentlich eine Turingmaschine?
Eine Turingmaschine ist ein Modellrechner, mit dem man versucht, maschinelle Berechenbarkeit mit einfachen Mitteln zu beschreiben. Inwieweit das gelungen ist, soll in Abschnitt Church-Turing-These genauer erläutert werden. Die Turingmaschine wurde 1936 vom britischen Mathematiker Alan Turing entwickelt - interessanterweise bevor es die ersten realen Computer gab. Es gibt eine Vielzahl an Turingmaschinenvarianten. Wir betrachten zunächst eine sehr einfache Variante.
Eine (Ein-Band-) Turingmaschine verfügt über ein nach rechts und links unbegrenztes Band, das in einzelne Felder aufgeteilt ist. In diesen Feldern können Symbole einer vorgegebenen Symbolmenge abgelegt werden. Die einzelnen Felder des Bandes können mit einem Lese-/Schreibkopf angesteuert werden. Dieser Lese-/Schreibkopf kann den Inhalt eines Feldes lesen und auch Symbole in die Felder schreiben. Zudem kann er sich jeweils einen Schritt nach rechts und nach links bewegen. Die Verarbeitungseinheit zur Steuerung des Lese-/Schreibkopfes befindet sich stets in einem bestimmten Zustand. Die Verarbeitung selbst wird über ein Steuerprogramm festgelegt.
Die Arbeitsweise einer Turingmaschine soll anhand einer konkreten Verarbeitungsaufgabe erläutert werden.
Die Turingmaschine befindet sich zunächst im Anfangszustand. Auf dem Band befinden sich die Symbole, die verarbeitet werden sollen. Im vorliegenden Beispiel sind das die Symbole "0" und "1", mit denen hier eine Dualzahl dargestellt ist. Der Lese-/Schreibkopf verarbeitet jetzt Schritt für Schritt die Symbole auf dem Band gemäß des Steuerprogramms.
Fachkonzept - Turingmaschine
Das Verhalten einer Turingmaschine beschreibt man oft mit einem Zustandsdiagramm:
Die Turingmaschine hat eine nichtleere endliche Menge Z von Zuständen. Im vorliegenden Fall ist das die Menge
Z = {q0, q1, q2, q3, q4, q5}. Der Zustand q0 ist hier als Anfangszustand ausgezeichnet,
der Zustand q5 als ein Endzustand.
Eine Verarbeitung wird durch einen Zustandsübergang (von einem Zustand in einen anderen, gegebenenfalls denselben Zustand) beschrieben. Ein Zustandsübergang erfolgt nur in Abhängigkeit vom gelesenen Symbol. Ein Zustandsübergang beschreibt zusätzlich, wie das gelesene Symbol überschrieben wird (ggf. durch dasselbe Symbol) und wie sich anschließend der Lese-Schreibkopf bewegt. R steht für einen Schritt nach rechts und L für einen Schritt nach links. Im Zustandsdiagramm werden diese Informationstripel in der Gestalt (gelesenes Symbol; geschriebenes Symbol, Bewegung) an die Übergangspfeile geschrieben. Die Bedeutung dieser Informationstripel soll anhand konkreter Beispiele weiter erläutert werden.
Das Tripel 0;0,R bedeutet: Wenn das Symbol 0 gelesen wird, dann überschreibe es
mit dem Symbol 0 und bewege den Lese-/Schreibkopf eine Zelle nach rechts.
Das Tripel ∅;∅,L bedeutet: Wenn das Symbol ∅ gelesen wird,
dann überschreibe es mit dem Symbol ∅ und bewege den Lese-/Schreibkopf eine Zelle nach links.
Beachte, dass oft ein Symbol zur Beschreibung eines leeren Feldes benötigt wird.
Im Beispiel oben wurde hierzu das Symbol ∅ benutzt.
Wir werden im Folgenden oft auch das Symbol B ("blank") für diesen Zweck einführen.
Zusammenfassend lässt sich das Verarbeitungsmodell Turingmaschine
wie folgt charakterisieren.
Eine (einfache) Turingmaschine ist eine Verarbeitungseinheit, die durch folgende Bestandteile festgelegt wird:
- eine nichtleere, endliche Menge von Zuständen
- eine nichtleere, endliche Menge von Eingabesymbolen,
die das Symbol
B(für ein leeres Feld) nicht enthält - eine nichtleere, endliche Menge von Bandsymbolen,
die alle Eingabesymbole, gegebenenfalls weitere Hilfssymbole und das Symbol
Bfür ein leeres Feld enthält - eine Überführungsfunktion, die dem aktuellem Zustand in Abhängigkeit von einem gelesenen Symbol den Folgezustand zuordnet, zudem das zu schreibende Symbol und die Bewegung des Lese-Schreibkopfes festlegt
- einen ausgezeichneten Zustand - den Anfangszustand -
- eine Menge von Endzuständen
Beachte, dass hier das Verarbeitungsmodell deterministische Turingmaschine
festgelegt wird.
Mit dem Zusatz einfach
soll hervorgehoben werden, dass wir eine sehr einfache Turingmaschinenvariante
betrachten.
Turingmaschinenvarianten
Es gibt eine Vielzahl von Turingmaschinenvarianten, die sich in der Anordnung der Felder, der Anzahl der Lese-/Schreibköpfe, der Anzahl der pro Zustandsübergang erlaubten Elementaroperationen usw. unterscheiden. Wir haben bereits die folgende zweidimensionale Variante betrachtet:
Statt eines eindimensionalen Bandes ist die Welt hier durch ein zweidimensionales Raster gegebenen.
Beachte auch, dass bei der hier betrachteten Turingmaschinen mehrere Elementaroperationen bei einem Zustandsübergang erlaubt sind.
Kara kann man als spielerische Variante dieser zweidimensionalen Turingmaschine auffassen. Der Marienkäfer Kara übernimmt hier die Rolle des Lese-/Schreibkopfes. Beachte, dass die Anzahl der zu verarbeitenden Symbole hier sehr stark eingeschränkt ist: Kara kann nur ein Symbol - das Kleeblatt - verarbeiten.
Wir werden im Folgenden - je nach Anwendungskontext - mit verschiedenen Turingmaschinenvarianten arbeiten.
Mächtigkeit der Turingmaschinenvarianten
Inwieweit beeinflussen die Festlegungen zur Turingmaschine (wie Ein-Band/Mehr-Band/mehrdimensional, Anzahl der Lese-/Schreibköpfe, ...) ihre Mächtigkeit beim Problemlösen?
Man kann den folgenden fundamentalen Zusammenhang zeigen.
Satz (über die Gleichmächtigkeit von Turingmaschinenvarianten)
Alle (hier betrachteten) Turingmaschinenvarianten sind im folgenden Sinn gleichmächtig: Ein Problem ist genau dann mit einer einfachen Turingmaschine lösbar, wenn es mit einer zweidimensionalen Turingmaschine lösbar ist, genau dann, wenn es mit einer ...-Turingmaschinenvariante lösbar ist.
Zur Klärung prinzipieller Fragestellungen ist es daher unerheblich, welche Turingmaschinenvariante man benutzt.