Mehrspuren-Turingmaschine

Grundidee und Bedeutung

Eine Mehrspuren-Turingmaschine (englisch Multi-track Turing machine) ist ein abstraktes Maschinenmodell der theoretischen Informatik und erweitert die klassische Turingmaschine. Sie besitzt ein einziges Speicherband, das pro Bandfeld mehrere Spuren hat. Ein Bandfeld enthält daher gleichzeitig mehrere Symbole, eines je Spur.

Es gibt jedoch nur einen Lese- und Schreibkopf. Er liest und schreibt bei jedem Schritt stets alle k Symbole eines Feldes und bewegt sich anschließend für alle Spuren gemeinsam und synchron nach links, nach rechts oder gar nicht. Das unterscheidet die Mehrspuren-Turingmaschine wesentlich von einer Mehrband-Turingmaschine: Bei dieser gibt es mehrere Köpfe, deren Bewegungen getrennt festgelegt werden können.

Abgesehen davon arbeitet eine Mehrspuren-Turingmaschine wie eine klassische Turingmaschine. Eine Maschine mit nur einer Spur entspricht genau einer klassischen Turingmaschine. Außerdem kann jede Mehrspuren-Turingmaschine durch eine klassische Turingmaschine mit einem Band simuliert werden. Beide Modelle sind deshalb bezüglich der Berechenbarkeit von Funktionen äquivalent: Sie können dieselben Funktionen berechnen.

Formale Beschreibung

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

• Q ist die endliche Zustandsmenge.
• Σ ist das endliche Eingabealphabet.
• Γ ist das endliche Bandalphabet; es gilt Σ ⊂ Γ.
• q₀ ∈ Q ist der Anfangszustand.
• □ ∈ Γ \ Σ ist das Blank, also das Symbol für ein leeres Feld.
• F ⊆ Q ist die Menge der Endzustände.
• δ : (Q \ F) × Γᵏ → Q × Γᵏ × {L, N, R} ist die partielle Überführungsfunktion. „Partiell“ bedeutet hier, dass nicht für jede mögliche Eingabe zwingend ein Übergang definiert sein muss.

Die Überführungsfunktion erhält den aktuellen Zustand und die k aus einem Bandfeld gelesenen Symbole. Sie bestimmt dann den nächsten Zustand, die k Symbole, die in das aktuelle Feld geschrieben werden, sowie eine Kopfbewegung: L bedeutet ein Feld nach links, N keine Bewegung und R ein Feld nach rechts.

Gegenüber einer klassischen Turingmaschine werden also k Symbole statt eines Symbols gelesen und geschrieben. Gegenüber einer Mehrband-Turingmaschine gibt es nur eine Bewegungsrichtung, weil nur ein gemeinsamer Lese- und Schreibkopf vorhanden ist; bei einer Mehrband-Turingmaschine würden k Bewegungsrichtungen, jeweils für einen Kopf, festgelegt.

Für eine nichtdeterministische k-Spuren-Turingmaschine wird die Überführungsfunktion durch die Übergangsrelation δ ⊆ (Q \ F) × Γᵏ × Q × Γᵏ × {L, N, R} ersetzt.

Beispiel: Addition auf drei Spuren

Das Beispiel beschreibt eine 3-Spuren-Turingmaschine, die zwei gleich lange Binärzahlen addiert. Zu Beginn stehen die beiden Zahlen auf der ersten und zweiten Spur; die dritte Spur nimmt die Ausgabe auf. Die Maschine ist M = ({q₀, q₁, q₂, q_f}, {0, 1}, {0, 1, b}, δ, q₀, b, {q_f}).

Zunächst bewegt sich die Maschine in q₀ nach rechts bis hinter das Ende der Eingabe. Dabei lässt sie die gelesenen Symbole unverändert. Beim Dreifach-Blank b, b, b wechselt sie nach q₁ und bewegt sich ein Feld nach links; der Kopf steht dann auf der letzten Eingabeziffer.

Die Addition erfolgt von rechts nach links. q₁ steht für eine Addition ohne Übertrag aus dem vorherigen Schritt, q₂ für eine Addition mit Übertrag.

• In q₁ ergibt 0 + 0 die Ausgabebit 0 und die Maschine bleibt in q₁. Die Kombinationen 0 + 1 und 1 + 0 ergeben jeweils 1 und führen ebenfalls zu q₁. Bei 1 + 1 wird 0 geschrieben und die Maschine wechselt wegen des Übertrags zu q₂.
• In q₂ wird der Übertrag mitgerechnet: 0 + 0 ergibt 1 und führt zu q₁; 0 + 1 sowie 1 + 0 ergeben 0 und die Maschine bleibt in q₂; 1 + 1 ergibt 1 und die Maschine bleibt ebenfalls in q₂.
• Wird in q₁ ein Blank auf beiden Eingabespuren erreicht, hält die Maschine in q_f. Wird in q₂ ein solches Blank erreicht, schreibt sie zusätzlich eine 1 auf die Ausgabespur und hält in q_f.

Für 0011 und 1010 entsteht auf der dritten Spur b1101b. Die beiden Eingabespuren bleiben b0011b und b1010b. Der Ablauf erreicht nach den Schritten 7 bis 10 nacheinander die bislang berechneten Ausgabeteile 1, 01, 101 und 1101; anschließend hält die Maschine in q_f.

Simulation mit einer klassischen Turingmaschine

Jede k-Spuren-Turingmaschine Mᵏ = (Q, Σ, Γ, δ, q₀, □, F) lässt sich durch eine klassische Turingmaschine M = (Q, Σ, Γ′, δ′, q₀, □ᵏ, F) simulieren. Die Zustandsmenge und damit die Zustände bleiben unverändert. Statt mehrerer Spuren verwendet die klassische Maschine ein größeres Bandalphabet, dessen Symbole ganze k-Tupel von Bandsymbolen darstellen.

Formal gilt Γ′ = Γᵏ ∪ Σ. Ein Symbol aus Γᵏ kodiert also den Inhalt aller k Spuren eines ursprünglichen Feldes. Das Blank von M ist das Tupel (□, □, …, □), das nur Blanksymbole enthält.

Die Übergänge werden im Wesentlichen übernommen. Für γ_k ∈ Γᵏ gilt: (q, γ_k, q′, γ_k, D) ∈ δ′ genau dann, wenn (q, γ_k, q′, γ_k, D) ∈ δ. Die Überführungsfunktion beziehungsweise Übergangsrelation muss zusätzlich auf die Eingabesymbole Σ erweitert werden. Für σ ∈ Σ wird σ so behandelt wie das Tupel (σ, □, …, □): (q, σ, q′, γ_k, D) ∈ δ′ genau dann, wenn (q, (σ, □, …, □), q′, γ_k, D) ∈ δ.

Damit kann ein einzelnes Symbol der klassischen Maschine den gleichzeitigen Inhalt aller Spuren eines Mehrspuren-Bandfeldes speichern.