Mehrspuren-Turingmaschine

Eine Mehrspuren-Turingmaschine (englisch Multi-track Turing machine) i​st eine abstrakte Maschine i​n der theoretischen Informatik u​nd eine Erweiterung d​er klassischen Turingmaschine.

3 Spuren-Turing-Maschine

Die Mehrspuren-Turingmaschine verfügt über e​in Speicherband m​it mehreren Spuren, d. h., p​ro Feld können mehrere Symbole ausgelesen werden, a​ber nur e​inen Lese- u​nd Schreibkopf. Dieser Schreibkopf liest/schreibt i​mmer alle Spuren e​ines Feldes a​m Band u​nd bewegt s​ich dann für a​lle Spuren synchron (ein wesentlicher Unterschied z​u Mehrband-Turingmaschinen). Ansonsten verhalten s​ich Mehrspuren-Turingmaschinen g​enau so w​ie klassische Turingmaschinen.

Eine Mehrspuren-Turingmaschine mit nur einem Band entspricht genau der klassischen Turingmaschine und jede Mehrspuren-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.

Formale Definition

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

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

Die Definition unterscheidet sich von der einer klassischen Turingmaschine (oder auch einer Mehrband-Turingmaschine) nur in der Definition der Überführungsfunktion. Die partielle Überführungsfunktion ${\displaystyle \delta }$ liefert zu einem Zustand und den k aus einem Feld gelesenen Bandsymbolen (i) den nächsten Zustand, (ii) k Bandsymbole das in das aktuelle Feld geschrieben werden, und (iii) die Bewegungsrichtung des Lese-Schreib-Kopf (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. Der Unterschied zur Mehrband-Turingmaschine besteht darin, dass ${\displaystyle \delta }$ nur eine Bewegungsrichtung für den Lese-Schreib-Kopf festlegt, während ${\displaystyle \delta }$ bei Mehrband-Turingmaschinen k Bewegungsrichtungen festlegt (eine für jeden Lese-Schreib-Kopf).

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

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

Beispiel

Das folgende Beispiel ist eine 3 Spuren Turingmaschine, die 2 gleich lange Binärzahlen addiert. Dabei sind zu Beginn die zwei gegebenen Zahlen in den ersten beiden Spuren gespeichert und die Ausgabe wird in die dritte Spur gespeichert. ${\displaystyle M=(\{q_{0},q_{1},q_{2},q_{f}\},\{0,1\},\{0,1,b\},\delta ,q_{0},b,\{q_{f}\})}$

Die Überführungsfunktion ${\displaystyle \delta }$ definieren wir schrittweise. Im Zustand ${\displaystyle q_{0}}$ bewegt sich die Maschine an das rechte Ende der Eingabe. Wenn die Maschine den Zustand ${\displaystyle q_{0}}$ verlassen hat, steht der Lese-Schreib-Kopf auf der letzten Ziffer der Eingabe.

aktueller Zustand	geles. Symbol				schr. Symbol			neuer Zustand	Kopf- richtung
${\displaystyle q_{0}}$	0	0	b	→	0	0	b	${\displaystyle q_{0}}$	R
${\displaystyle q_{0}}$	0	1	b	→	0	1	b	${\displaystyle q_{0}}$	R
${\displaystyle q_{0}}$	1	0	b	→	1	0	b	${\displaystyle q_{0}}$	R
${\displaystyle q_{0}}$	1	1	b	→	1	1	b	${\displaystyle q_{0}}$	R
${\displaystyle q_{0}}$	b	b	b	→	b	b	b	${\displaystyle q_{1}}$	L

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

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

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

Wir betrachten a​ls Beispiel d​ie Addition v​on 0011 u​nd 1010

Schritt	Zust.	Band-Spuren
1	${\displaystyle q_{0}}$	b0011b
		b1010b
		bbbbbb
2	${\displaystyle q_{0}}$	b0011b
		b1010b
		bbbbbb
3	${\displaystyle q_{0}}$	b0011b
		b1010b
		bbbbbb
4	${\displaystyle q_{0}}$	b0011b
		b1010b
		bbbbbb
5	${\displaystyle q_{0}}$	b0011b
		b1010b
		bbbbbb
6	${\displaystyle q_{1}}$	b0011b
		b1010b
		bbbbbb

Schritt	Zust.	Band-Spuren
7	${\displaystyle q_{1}}$	b0011b
		b1010b
		bbbb1b
8	${\displaystyle q_{2}}$	b0011b
		b1010b
		bbb01b
9	${\displaystyle q_{1}}$	b0011b
		b1010b
		bb101b
10	${\displaystyle q_{1}}$	b0011b
		b1010b
		b1101b
hält	${\displaystyle q_{f}}$	b0011b
		b1010b
		b1101b

Simulation durch eine klassische Turingmaschine

Jede k-Spuren-Turingmaschine ${\displaystyle M^{k}=(Q,\Sigma ,\Gamma ,\delta ,q_{0},\square ,F)}$ kann durch ein Turingmaschine ${\displaystyle M=(Q,\Sigma ,\Gamma ',\delta ',q_{0},\square ^{k},F)}$ simuliert werden. Dabei bleiben die Zustände der Maschine unverändert, aber für die klassische Turingmaschine wird ein größeres Bandalphabet zu verwenden sein, das (1) alle k-Tupel über Gamma und (2) das Eingabealphabet enthält. Die Überführungsfunktion oder Übergangsrelation wird eigentlich unverändert übernommen werden, muss aber auf ${\displaystyle \Sigma }$ erweitert werden. Ein Symbol ${\displaystyle a\in \Sigma }$ wird in der konstruierten Turingmaschine wie das k-Tupel ${\displaystyle (a,\square ,\dotsc ,\square )}$ behandelt. Als Blanksymbol der Turingmaschine M fungiert das k-Tupel ${\displaystyle (\square ,\square ,\dotsc ,\square ),}$ das nur Blanksymbole enthält. Formal kann das wie folgt ausgedrückt werden:

• ${\displaystyle \Gamma '=\Gamma ^{k}\cup \Sigma }$
• Für ${\displaystyle \gamma _{k}\in \Gamma ^{k}}$ gilt ${\displaystyle (q,\gamma _{k},q',\gamma _{k},D)\in \delta '}$ genau dann, wenn ${\displaystyle (q,\gamma _{k},q',\gamma _{k},D)\in \delta .}$
• Für ${\displaystyle \sigma \in \Sigma }$ gilt ${\displaystyle (q,\sigma ,q',\gamma _{k},D)\in \delta '}$ genau dann, wenn ${\displaystyle (q,(\sigma ,\square ,\dotsc ,\square ),q',\gamma _{k},D)\in \delta .}$

Literatur

• Ingo Wegener: Theoretische Informatik. Eine algorithmenorientierte Einführung. B.G. Teubner, Stuttgart, ISBN 3-519-02123-4, 2. Turingmaschinen, Churchsche These und Entscheidbarkeit.
• Thomas A. Sudkamp: Languages and Machines. An Introduction to the Theory of Computer Science. Second edition Auflage. Addison-Wesley, 1998, ISBN 0-201-82136-2, 9.4. Multitrack Machines.