Mehrband-Turingmaschine

Eine Mehrband-Turingmaschine (englisch Multitape Turing machine) ist eine abstrakte Maschine in der theoretischen Informatik und eine Erweiterung der klassischen Turingmaschine.

3-Band-Turing-Maschine

Die Mehrband-Turingmaschine verfügt über mehrere Speicherbänder, die jeweils einen eigenen Lese- und Schreibkopf besitzen, wobei diese Lese- und Schreibköpfe unabhängig voneinander bewegt werden können (ein wesentlicher Unterschied zur Mehrspuren-Turingmaschine). Ansonsten verhält sich eine Mehrband-Turingmaschine genau so wie eine klassische Turingmaschine.

Eine Mehrband-Turingmaschine mit nur einem Band entspricht genau der klassischen Turingmaschine und jede Mehrband-Turingmaschine kann durch eine klassische Turingmaschine (mit nur einem Band) simuliert werden. Die beiden Maschinenmodelle sind also bezüglich der Berechenbarkeit von Funktionen äquivalent, d. h., beide Modelle können die gleichen Funktionen berechnen.

Die Mehrband-Turingmaschine arbeitet im Allgemeinen effizienter als eine Einband-Maschine, aber nicht entscheidend im Sinne der wichtigsten Fragen der Komplexitätstheorie, d. h., vor allem für die Frage, welche Probleme in Polynomialzeit gelöst werden können: Eine Mehrband-Maschine, die ein Problem in Polynomialzeit löst, kann von einer Einband-Maschine in Polynomialzeit simuliert werden, wobei aber im Allgemeinen der Grad des die Laufzeit beschränkenden Polynoms höher ist.

Formale Definition

Formal kann eine (deterministische) k-Band-Turingmaschine als Tupel $M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},\square ,F)$ dargestellt werden.

• $Q$ ist die endliche Zustandsmenge.
• $\Sigma$ ist das endliche Eingabealphabet.
• $\Gamma$ ist das endliche Bandalphabet und es gilt $\Sigma \subset \Gamma$.
• $\delta \colon (Q\setminus F)\times \Gamma ^{k}\to Q\times \Gamma ^{k}\times \{L,N,R\}^{k}$ ist die (partielle) Überführungsfunktion.
• $q_{0}\in Q$ ist der Anfangszustand.
• $\square \in \Gamma \setminus \Sigma$ steht für das leere Feld (Blank).
• $F\subseteq Q$ die Menge der Endzustände.

Die Definition unterscheidet sich von der einer klassischen Turingmaschine (oder auch einer Mehrspuren-Turingmaschine) nur in der Definition der Überführungsfunktion $\delta$. Die Überführungsfunktion $\delta$ liefert zu einem Zustand und den k von den verschiedenen Bändern gelesenen Bandsymbolen (i) den nächsten Zustand, (ii) k Bandsymbole, die in das aktuelle Feld geschrieben werden, und (iii) die k Bewegungsrichtungen der Lese-Schreib-Köpfe (L … ein Feld nach links, N … nicht bewegen, R … ein Feld nach rechts). Im Kontrast zur klassischen Turingmaschine werden k Symbole statt nur einem Symbol gelesen und geschrieben und k Lese-Schreib-Köpfe bewegt. Der Unterschied zur Mehrspuren-Turingmaschine besteht darin, dass $\delta$ k Bewegungsrichtungen festlegt (eine für jeden Lese-Schreib-Kopf), während $\delta$ bei Mehrspuren-Turingmaschinen nur eine Bewegungsrichtung für den Lese-Schreib-Kopf festlegt, der sich auf allen Spuren gleich bewegt.

Um eine nichtdeterministische Variante der k-Band-Turingmaschine zu definieren, ersetzt man die Überführungsfunktion durch eine Übergangsrelation $\delta$:

• $\delta \subseteq (Q\setminus F)\times \Gamma ^{k}\times Q\times \Gamma ^{k}\times \{L,N,R\}^{k}$

Beispiel

Das folgende Beispiel ist eine 3-Band-Turingmaschine, die zwei Binärzahlen addiert. Dabei sind zu Beginn die zwei gegebenen Zahlen auf den ersten beiden Bändern gespeichert und die Ausgabe wird am dritten Band gespeichert. $M=(\{q_{0},q_{1},q_{2},q_{f}\},\{0,1\},\{0,1,b\},\delta ,q_{0},b,\{q_{f}\})$

Die Überführungsfunktion $\delta$ wird schrittweise definiert. Im Zustand $q_{0}$ bewegt die Maschine die Lese-Schreib-Köpfe der ersten beiden Bänder an das rechte Ende der Eingabe. Wenn die Maschine den Zustand $q_{0}$ verlassen hat, stehen die Lese-Schreib-Köpfe auf der jeweils letzten Ziffer der Eingabe.

aktueller Zustand	geles. Symbol				schr. Symbol			neuer Zustand	Kopf- richtungen
$q_{0}$	b	0	b	→	b	0	b	$q_{0}$	N	R	N
$q_{0}$	b	1	b	→	b	1	b	$q_{0}$	N	R	N
$q_{0}$	0	b	b	→	0	b	b	$q_{0}$	R	N	N
$q_{0}$	0	0	b	→	0	0	b	$q_{0}$	R	R	N
$q_{0}$	0	1	b	→	0	1	b	$q_{0}$	R	R	N
$q_{0}$	1	b	b	→	1	b	b	$q_{0}$	R	N	N
$q_{0}$	1	0	b	→	1	0	b	$q_{0}$	R	R	N
$q_{0}$	1	1	b	→	1	1	b	$q_{0}$	R	R	N
$q_{0}$	b	b	b	→	b	b	b	$q_{1}$	L	L	N

Für die eigentliche Addition werden die zwei Zustände $q_{1}$ und $q_{2}$ verwendet. Hier entspricht $q_{1}$ der Addition an der aktuellen Stelle ohne Übertragsbit aus dem vorherigen Schritt und $q_{2}$ der Addition mit einem Übertragsbit aus dem letzten Schritt. Wir definieren schließlich noch $\delta$ für $q_{1}$ und $q_{2}$.

aktueller Zustand	geles. Symbol				schr. Symbol			neuer Zustand	Kopf- richtungen
$q_{1}$	b	0	b	→	b	0	0	$q_{1}$	N	L	L
$q_{1}$	b	1	b	→	b	1	1	$q_{1}$	N	L	L
$q_{1}$	0	b	b	→	0	b	0	$q_{1}$	L	N	L
$q_{1}$	0	0	b	→	0	0	0	$q_{1}$	L	L	L
$q_{1}$	0	1	b	→	0	1	1	$q_{1}$	L	L	L
$q_{1}$	1	b	b	→	1	b	1	$q_{1}$	L	N	L
$q_{1}$	1	0	b	→	1	0	1	$q_{1}$	L	L	L
$q_{1}$	1	1	b	→	1	1	0	$q_{2}$	L	L	L
$q_{1}$	b	b	b	→	b	b	b	$q_{f}$	R	R	R

aktueller Zustand	geles. Symbol				schr. Symbol			neuer Zustand	Kopf- richtungen
$q_{2}$	b	0	b	→	b	0	1	$q_{1}$	N	L	L
$q_{2}$	b	1	b	→	b	1	0	$q_{2}$	N	L	L
$q_{2}$	0	b	b	→	0	b	1	$q_{1}$	L	N	L
$q_{2}$	0	0	b	→	0	0	1	$q_{1}$	L	L	L
$q_{2}$	0	1	b	→	0	1	0	$q_{2}$	L	L	L
$q_{2}$	1	b	b	→	1	b	0	$q_{2}$	L	N	L
$q_{2}$	1	0	b	→	1	0	0	$q_{2}$	L	L	L
$q_{2}$	1	1	b	→	1	1	1	$q_{2}$	L	L	L
$q_{2}$	b	b	b	→	b	b	1	$q_{f}$	R	R	N

Wir betrachten als Beispiel die Addition von 11 und 1010.

Schritt	Zust.	Bänder
1	$q_{0}$	b11b
		b1010b
		bbbbb
2	$q_{0}$	b11b
		b1010b
		bbbbb
3	$q_{0}$	b11b
		b1010b
		bbbbb
4	$q_{0}$	b11b
		b1010b
		bbbbb
5	$q_{0}$	b11b
		b1010b
		bbbbb
6	$q_{1}$	b11b
		b1010b
		bbbbb

Schritt	Zust.	Bänder
7	$q_{1}$	b11b
		b1010b
		bbbb1
8	$q_{2}$	b11b
		b1010b
		bbb01b
9	$q_{1}$	b11b
		b1010b
		bb101b
10	$q_{1}$	b11b
		b1010b
		b1101b
hält	$q_{f}$	b11b
		b1010b
		b1101b

Literatur

• John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. 3., aktualisierte Auflage. Pearson Studium, München 2011, ISBN 978-3-86894-082-4, 8.4. Erweiterungen für die einfache Turing-Maschine (englisch: Introduction to Automata Theory, Languages, and Computation. 2007. Übersetzt von Sigrid Richter und Ingrid Tokar). 
• Ingo Wegener: Theoretische Informatik. Eine algorithmenorientierte Einführung. B.G. Teubner, Stuttgart, ISBN 3-519-02123-4, 2. Turingmaschinen, Churchsche These und Entscheidbarkeit. 
• Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach. Cambridge University Press, Cambridge; New York 2009, ISBN 978-0-521-42426-4, 1.2. The Turing Machine (Draft [PDF; abgerufen am 30. Juli 2016]).