Mehrband-Turingmaschine

Kernidee und Bedeutung

Eine Mehrband-Turingmaschine (englisch: Multitape Turing machine) ist eine abstrakte Maschine der theoretischen Informatik und eine Erweiterung der klassischen Turingmaschine. Sie besitzt mehrere Speicherbänder. Jedes Band hat einen eigenen Lese- und Schreibkopf; diese Köpfe können unabhängig voneinander bewegt werden. Dadurch können in einem Rechenschritt mehrere Bandsymbole gleichzeitig gelesen und bearbeitet werden.

Eine Mehrband-Turingmaschine mit nur einem Band entspricht genau der klassischen Turingmaschine. Umgekehrt kann jede Mehrband-Turingmaschine durch eine klassische Einband-Turingmaschine simuliert werden. Beide Modelle sind deshalb bezüglich der Berechenbarkeit von Funktionen äquivalent: Sie können genau dieselben Funktionen berechnen.

Mehrband-Turingmaschinen arbeiten im Allgemeinen effizienter als Einbandmaschinen. Für zentrale Fragen der Komplexitätstheorie ergibt sich jedoch kein entscheidender Unterschied. Insbesondere gilt: Löst eine Mehrbandmaschine ein Problem in Polynomialzeit, kann eine Einbandmaschine sie ebenfalls in Polynomialzeit simulieren. Im Allgemeinen ist dabei jedoch der Grad des Polynoms, das die Laufzeit beschränkt, höher.

Formale Bestandteile

Eine deterministische k-Band-Turingmaschine wird formal als Tupel M=(Q,Σ,Γ,δ,q₀,□,F) dargestellt.

• Q ist die endliche Zustandsmenge.
• Σ ist das endliche Eingabealphabet.
• Γ ist das endliche Bandalphabet; es gilt Σ ⊆ Γ.
• δ ist die partielle Überführungsfunktion: δ: (Q\F) × Γᵏ → Q × Γᵏ × {L,N,R}ᵏ.
• q₀ ∈ Q ist der Anfangszustand.
• □ ∈ Γ\Σ bezeichnet das leere Feld (Blank).
• F ⊆ Q ist die Menge der Endzustände.

Die Definition unterscheidet sich von der einer klassischen Turingmaschine oder einer Mehrspuren-Turingmaschine nur durch die Überführungsfunktion δ. Sie erhält einen Zustand und die k Symbole, die von den verschiedenen Bändern gelesen wurden. Als Ergebnis liefert sie (i) den nächsten Zustand, (ii) k Bandsymbole, die in die aktuellen Felder geschrieben werden, und (iii) die k Bewegungsrichtungen der Lese-Schreib-Köpfe.

Dabei bedeutet L, dass ein Kopf ein Feld nach links bewegt wird, N, dass er sich nicht bewegt, und R, dass er ein Feld nach rechts bewegt wird. Im Unterschied zur klassischen Turingmaschine werden k Symbole statt nur eines gelesen und geschrieben und k Köpfe bewegt.

Abgrenzung und Nichtdeterminismus

Der wesentliche Unterschied zu einer Mehrspuren-Turingmaschine liegt in der Bewegung der Köpfe. Bei einer Mehrband-Turingmaschine legt δ für jeden Lese-Schreib-Kopf eine eigene Bewegungsrichtung fest, also k Richtungen. Bei einer Mehrspuren-Turingmaschine gibt δ dagegen nur eine Bewegungsrichtung für den einzigen Lese-Schreib-Kopf vor; dieser bewegt sich auf allen Spuren gleich.

Für eine nichtdeterministische k-Band-Turingmaschine wird die Überführungsfunktion durch eine Übergangsrelation δ ersetzt:

δ ⊆ (Q\F) × Γᵏ × Q × Γᵏ × {L,N,R}ᵏ.

Diese Relation kann zu einem Zustand und den gelesenen k Bandsymbolen mehrere mögliche Folgezustände, Schreibvorgänge und Bewegungsrichtungen festlegen.

Beispiel: Addition zweier Binärzahlen

Das Beispiel ist eine 3-Band-Turingmaschine, die zwei Binärzahlen addiert. Zu Beginn steht die erste Zahl auf dem ersten Band und die zweite Zahl auf dem zweiten Band; das Ergebnis wird auf dem dritten Band gespeichert. Die Maschine ist definiert als

M=({q₀,q₁,q₂,q_f},{0,1},{0,1,b},δ,q₀,b,{q_f}).

Das Symbol b dient hier als Blank. Die Zustände q₀, q₁, q₂ und q_f sind die Zustände der Maschine, wobei q_f der Endzustand ist.

Im Zustand q₀ bewegen die Köpfe des ersten und zweiten Bandes sich jeweils zum rechten Ende der Eingabe. Je nach gelesenem Symbol bleiben die Köpfe stehen oder bewegen sich nach rechts; der dritte Kopf bleibt dabei unbewegt. Sobald auf beiden Eingabebändern ein Blank gelesen wird, schreibt die Maschine weiterhin b, wechselt nach q₁ und bewegt die ersten beiden Köpfe jeweils ein Feld nach links. Danach beginnt die eigentliche Addition von rechts nach links.

q₁ steht für die Addition an der aktuellen Stelle ohne Übertragsbit aus dem vorherigen Schritt. Die Binärregeln sind unter anderem: 0+0 ergibt 0, 0+1 und 1+0 ergeben 1, und 1+1 ergibt 0 mit Wechsel nach q₂, weil ein Übertrag entsteht. q₂ steht für die Addition mit einem Übertragsbit. Dort wird der Übertrag berücksichtigt; beispielsweise ergibt 1+1 mit Übertrag 1, wobei q₂ beibehalten wird. Die Köpfe der ersten beiden Bänder bewegen sich bei der Addition nach links, während der dritte Kopf das jeweilige Ergebnisbit schreibt.

Erreicht q₁ auf beiden Eingabebändern gleichzeitig das Blank, schreibt die Maschine b auf das dritte Band, wechselt nach q_f und bewegt alle drei Köpfe nach rechts. Erreicht q₂ diese Situation, schreibt sie stattdessen 1 auf das dritte Band, wechselt ebenfalls nach q_f und bewegt die ersten beiden Köpfe nach rechts, während der dritte Kopf unbewegt bleibt.

Als Ablaufbeispiel wird 11+1010 betrachtet. Nach den ersten fünf Schritten befindet sich die Maschine noch in q₀; in Schritt 6 wechselt sie nach q₁. In Schritt 7 wird auf dem dritten Band zunächst 1 geschrieben. In Schritt 8 wechselt die Maschine nach q₂ und das dritte Band enthält bbb01b. In Schritt 9 befindet sie sich wieder in q₁ und das dritte Band enthält bb101b. In Schritt 10 enthält es b1101b; die Maschine hält anschließend im Zustand q_f. Das Ergebnis der Addition ist somit 1101.