Turingmaschine: Aufbau, Ablauf und Grenzen

Stell dir ein in einzelne Zellen unterteiltes Band vor. Auf jeder Zelle steht genau ein Symbol. Ein beweglicher Kopf bearbeitet jeweils eine dieser Zellen.

Die wichtigsten Bestandteile sind:

• Das Band dient als Speicher. Es ist konzeptionell unbegrenzt und besteht aus einzelnen Zellen.
• Das Bandalphabet enthält alle Symbole, die auf dem Band stehen dürfen.
• Das Blank-Symbol □ kennzeichnet eine leere Zelle.
• Der Lese-Schreib-Kopf liest die aktuelle Zelle, kann sie überschreiben und sich nach links oder rechts bewegen. Je nach Modell darf er auch stehen bleiben.
• Die Zustandssteuerung besitzt endlich viele Zustände. Einer davon ist der Startzustand; weitere können als Endzustände dienen.
• Die Übergangsfunktion ist das Programm der Maschine. Sie legt für jede vorgesehene Kombination aus Zustand und gelesenem Symbol den nächsten Schritt fest.

Zu Beginn steht die Eingabe auf dem ansonsten leeren Band. Üblicherweise zeigt der Kopf auf das erste Eingabesymbol, und die Maschine befindet sich im Startzustand.

Ein Arbeitsschritt folgt immer demselben Muster:

$$(\text{Zustand},\text{gelesenes Symbol})\to(\text{Folgezustand},\text{Schreibsymbol},\text{Bewegung})$$

Die Bewegungen werden meist mit L für links, R für rechts und N oder S für stehen bleiben bezeichnet.

Die Regel

$$\delta(q_0,0)=(q_0,1,R)$$

bedeutet:

1. Die Maschine befindet sich in $q_0$ und liest 0.
2. Sie schreibt 1 auf die aktuelle Zelle.
3. Sie bewegt den Kopf eine Zelle nach rechts.
4. Sie bleibt im Zustand $q_0$.

Eine Konfiguration ist eine vollständige Momentaufnahme der Maschine. Dazu gehören der aktuelle Zustand, der relevante Bandinhalt und die Position des Kopfes.

Eine kompakte Schreibweise setzt den Zustand direkt vor das gerade gelesene Symbol. In 1 q_0 01 steht links vom Kopf eine 1; der Kopf liest die folgende 0.

Für eine zuverlässige Simulation gehst du immer gleich vor:

1. Markiere Zustand und Kopfposition.
2. Lies das aktuelle Symbol.
3. Suche die passende Übergangsregel.
4. Schreibe zuerst das angegebene Symbol.
5. Bewege danach den Kopf.
6. Notiere zuletzt den Folgezustand und die neue Konfiguration.

Nicht jede haltende Berechnung bedeutet automatisch Akzeptanz. Für Entscheidungsprobleme werden haltende Zustände häufig als akzeptierend oder verwerfend unterschieden.

• Akzeptieren: Die Maschine hält in einem akzeptierenden Endzustand.
• Verwerfen: Die Maschine hält, ohne einen akzeptierenden Endzustand erreicht zu haben.
• Nichtterminierung oder Divergenz: Die Maschine führt unendlich viele Schritte aus und hält nicht.

Eine Turingmaschine erkennt eine Sprache, wenn sie jedes zugehörige Wort nach endlich vielen Schritten akzeptiert. Bei einem Wort, das nicht zur Sprache gehört, darf sie verwerfen oder endlos weiterlaufen.

Eine Turingmaschine entscheidet eine Sprache nur dann, wenn sie bei jeder erlaubten Eingabe hält: Sie akzeptiert die Wörter der Sprache und verwirft alle anderen.

Bei einer gewöhnlichen Turingmaschine ist das Programm durch ihre Übergangsregeln festgelegt. Eine universelle Turingmaschine erhält dagegen zwei Dinge als Eingabe:

• die kodierte Beschreibung einer anderen Turingmaschine;
• die Eingabe, auf der diese Maschine arbeiten soll.

Die universelle Maschine simuliert dann Schritt für Schritt die beschriebene Maschine. Dieses Prinzip ähnelt einem Computer, der unterschiedliche gespeicherte Programme ausführt.

Es gibt Probleme, für die kein Turingmaschinen-Algorithmus existiert. Ein grundlegendes Beispiel ist das Halteproblem: Es gibt keinen Algorithmus, der für jede beliebige Turingmaschine und jede Eingabe immer korrekt entscheidet, ob die Maschine irgendwann halten wird.

Ein System heißt Turing-vollständig, wenn es – bei idealisiert unbegrenztem Speicher – die Berechnungen einer universellen Turingmaschine ausführen kann. Auch ein Turing-vollständiges System überwindet die Grenzen der Berechenbarkeit nicht.

Eine deterministische Ein-Band-Turingmaschine kann als 7-Tupel beschrieben werden:

$$M=(Q,\Sigma,\Gamma,\delta,q_0,\square,F)$$

Dabei bedeuten:

• $Q$: endliche Zustandsmenge;
• $\Sigma$: Eingabealphabet;
• $\Gamma$: Bandalphabet mit $\Sigma\subset\Gamma$;
• $q_0$: Startzustand;
• $\square$: Blank-Symbol, das nicht zum Eingabealphabet gehört;
• $F$: Menge akzeptierender Endzustände;
• $\delta$: partielle Übergangsfunktion.

Eine mögliche formale Schreibweise für die Übergangsfunktion ist:

$$\delta:(Q\setminus F)\times\Gamma\to Q\times\Gamma\times\{L,N,R\}$$

Partiell bedeutet, dass nicht für jede Kombination aus Zustand und Symbol eine Regel vorhanden sein muss. Fehlt eine Regel, hält die Maschine in dieser Konfiguration. Ob sie damit akzeptiert, hängt davon ab, ob ihr Zustand akzeptierend ist.

Andere Lehrwerke verwenden leicht veränderte Konventionen: S statt N, ein nur einseitig unendliches Band oder ein gemeinsames Alphabet für Eingabe und Band. Solche Varianten können dieselben berechenbaren Funktionen beschreiben, obwohl sie unterschiedlich viele Schritte oder unterschiedlich viel Speicher benötigen können.

Turingmaschinen können auch formale Sprachen verarbeiten. Die von ihnen erkennbaren Sprachen sind die rekursiv aufzählbaren beziehungsweise semientscheidbaren Sprachen des Typs 0. Die entscheidbaren Sprachen bilden darin die Teilmenge, für die eine passende Maschine bei jeder Eingabe hält.

Wenn du eine Turingmaschine untersuchst, stelle dir immer drei Fragen: Welche Konfiguration liegt vor? Welche Regel passt? Hält die entstehende Berechnung akzeptierend, verwerfend oder gar nicht?