3.3.3 Zurückführen der speziellen TM auf die klassische
Mehrbändige und Nichtdeterministische TM
Aus k-bändiger TM wird 2k-spurige TM
Mehrbändig und mehrköpfig (Multitape):
Für eine TM M1 mit k-Bändern und Köpfen lässt sich eine TM M2 mit 2k Spuren konstruieren.
Für jedes Band gibt es zwei Spuren - die eine enthält den Bandinhalt dieses Bandes von M1, die andere eine Markierung an der Stelle,
an der sich der Kopf befindet.
Der Zustand von M2 wird durch ein komplexes Symbol beschrieben,
der neben dem Zustand von M1 auch noch die Anzahl der Köpfmarkierungen rechts vom L/S-Kopf von M2 enthält.
Ablauf eines Zuges:
M2 startet mit dem Kopf auf der am weitesten links stehenden Kopfmarkierung.
Auf dem Weg des Kopfes nach links zu den verbleibenden Kopfsymbolen liest sie die jeweiligen Symbole unter den Kopfmarkierungen
(und verringert dabei entsprechend die Zahl der noch aufzusuchenden Markierungen).
Wurden alle Kopfzellen gelesen, kann der neue Zustand und die damit verbundenen Aktionen bestimmt werden.
Auf dem Weg nach links werden diese dann an jeder Kopfzelle ausgeführt.
Die am weitesten links stehende Kopfzelle wird wieder anhand der mit im Zustand vermerkten Zahl erkannt.
Der Zähler auf Band zwei arbeitet systematisch alle Alternativen ab.
Nichtdeterministische TM
Simulation einer nichtdeterministischen TM M1 durch eine deterministische TM M2 mit drei Bändern.
Auf dem ersten Band befindet sich die Eingabe, die auch nicht verändert wird.
Auf dem zweiten Band werden die Möglichkeiten eines Überganges generiert.
Die Nachfolgemöglichkeiten werden durchnummeriert von 1 ... n
(n ist die maximale Anzahl der Möglichkeiten für die Übergänge).
Hat eine Konfiguration weniger als die maximale Anzahl von Möglichkeiten, so bleiben diese einfach leer. Sei für eine TM δ(q1,a)={(q1,a,L), (q1,b,R),(q2,b,R)}
Für diesen Übergang gibt es drei Möglichkeiten, die nun mit 1, 2 und 3 nummeriert werden.)
Die Anzahl der möglichen Übergänge ist in jedem Fall endlich, da Zustandsmenge, Alphabet und Bewegungsrichtungen und somit auch ihre Kombination endlich sind.
Es werden nun systematisch Zahlenkombinationen generiert:
Die Zahl basiert auf dem n-adischen System.
Beginnend bei 0 (Startkonfiguration) bis n, darauf folgt der Umsprung in den zweistelligen Bereich mit 10 bis 1n usw.
So wird jede Möglichkeit in einer Breitensuche beachtet.
Von der Startkonfiguration wird jede Möglichkeit erst bis zur Tiefe 1, dann bis zur Tiefe 2, usw. verfolgt.
Auf dem dritten Band simuliert M2 die Aktionen von M1 anhand der Möglichkeiten auf Band 2 an einer Kopie der Eingabe.
Dabei bedeutet eine Zahl z1z2z3z4 auf Band 2 Folgendes:
Vom Eingangswort ausgehend wird die Alternative z1 probiert, an diesem Ergebnis die Alternative z2, nun Alternative z3 und schließlich - wieder am Ergebnis - Alternative z4.
Steht M2 am Ende in einem Endzustand, so hält sie.
Gerät sie zwischenzeitlich ins Stocken oder befindet sie sich am Ende der Simulation in keinem Endzustand, so wird zur Zahl auf Band 2 eine 1 hinzuaddiert.
Nun beginnt die Simulation wieder beim Anfangswort mit dem nächsten Wert.
1
2
Übersicht: Sprachklassen