Mehrspuren-Turingmaschine

Eine Erweiterung der klassischen Turingmaschine bei der das Speicherband über mehrere Spuren verfügt.

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

3 Spuren-Turing-Maschine

Die Mehrspuren-Turingmaschine verfügt über ein Speicherband mit mehreren Spuren, d. h., pro Feld können mehrere Symbole ausgelesen werden, aber nur einen Lese- und Schreibkopf. Dieser Schreibkopf liest/schreibt immer alle Spuren eines Feldes am Band und bewegt sich dann für alle Spuren synchron (ein wesentlicher Unterschied zu Mehrband-Turingmaschinen). Ansonsten verhalten sich Mehrspuren-Turingmaschinen genau so wie 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

Bearbeiten

Formal kann eine (deterministische) k-Spuren Turingmaschine als Tupel   dargestellt werden.

  •   ist die endliche Zustandsmenge.
  •   ist das endliche Eingabealphabet.
  •   ist das endliche Bandalphabet und es gilt  .
  •   ist die (partielle) Überführungsfunktion.
  •   ist der Anfangszustand.
  •   steht für das leere Feld (Blank).
  •   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   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   nur eine Bewegungsrichtung für den Lese-Schreib-Kopf festlegt, während   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  :

  •  

Beispiel

Bearbeiten

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.  

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

aktueller
Zustand
geles.
Symbol
  schr.
Symbol
neuer
Zustand
Kopf-
richtung
  0 0 b 0 0 b   R
  0 1 b 0 1 b   R
  1 0 b 1 0 b   R
  1 1 b 1 1 b   R
  b b b b b b   L

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

aktueller
Zustand
geles.
Symbol
  schr.
Symbol
neuer
Zustand
Kopf-
richtung
  0 0 b 0 0 0   L
  0 1 b 0 1 1   L
  1 0 b 1 0 1   L
  1 1 b 1 1 0   L
  b b b b b b   R
aktueller
Zustand
geles.
Symbol
  schr.
Symbol
neuer
Zustand
Kopf-
richtung
  0 0 b 0 0 1   L
  0 1 b 0 1 0   L
  1 0 b 1 0 0   L
  1 1 b 1 1 1   L
  b b b b b 1   N

Wir betrachten als Beispiel die Addition von 0011 und 1010

Schritt Zust. Band-Spuren
1   b0011b
b1010b
bbbbbb
2   b0011b
b1010b
bbbbbb
3   b0011b
b1010b
bbbbbb
4   b0011b
b1010b
bbbbbb
5   b0011b
b1010b
bbbbbb
6   b0011b
b1010b
bbbbbb
Schritt Zust. Band-Spuren
7   b0011b
b1010b
bbbb1b
8   b0011b
b1010b
bbb01b
9   b0011b
b1010b
bb101b
10   b0011b
b1010b
b1101b
hält   b0011b
b1010b
b1101b

Simulation durch eine klassische Turingmaschine

Bearbeiten

Jede k-Spuren-Turingmaschine   kann durch ein Turingmaschine   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   erweitert werden. Ein Symbol   wird in der konstruierten Turingmaschine wie das k-Tupel   behandelt. Als Blanksymbol der Turingmaschine M fungiert das k-Tupel   das nur Blanksymbole enthält. Formal kann das wie folgt ausgedrückt werden:

  •  
  • Für   gilt   genau dann, wenn  
  • Für   gilt   genau dann, wenn  

Literatur

Bearbeiten
  • 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.