|
Mehrspurig (multiple track):
Eine mehrspurige TM kann als einspurige aufgefasst werden.
Dann werden jeweils komplexe Symbole gelesen und verarbeitet.
Korrekte Symbole sind von der Form [a1,a2,...,ak] mit k = Anzahl der Spuren.
Ein Übergang ist dann durch ein Paar
(q, [a1,a2,...,ak]) = {(p, [b1,b2,...,bk,Bewegung])} gekennzeichnet.
Es ist möglich, dass Teile des komplexen Symbols gleich bleiben, also dass ai = bi.
|
 |
Einseitig beschränkt (TM with semi-infinite tape):
Die Simulation einer einseitig beschränkten TM durch eine unbeschränkte ist einfach:
Die Zelle links von der Startposition des Kopfes wird durch ein besonderes Symbol gekennzeichnet.
Wann immer während der Analyse diese Zelle erreicht wird, bricht die TM ohne zu akzeptieren ab.
Eine einseitig beschränkte TM M2 kann jedoch auch eine TM M1 mit beidseitig unbeschränktem Band simulieren:
Das Band wird so zu einem 2-spurigem Band gefaltet, dass es nach rechts hin unendlich ist.
Ganz links befindet sich in der oberen Spur die Nullzelle, in der unteren ein besonderes Symbol, dass den linken Rand markiert.
Die Übergangsfunktion von M2 gibt darüber Auskunft, ob M1 gerade eine obere (rechts vom Nullpunkt) oder eine untere (links vom Nullpunkt) Zelle bearbeiten würde.
Bei der Bewegung des Kopfes muss die neue Situation berücksichtigt werden:
Arbeitet die TM auf der unteren Spur, so müssen die Kopfbewegungen in die Gegenrichtung des Originalüberganges ausgeführt werden.
Eine Bewegung nach rechts der TM M1 bedeutet eine Bewegung hin zum Nullpunkt, also nach links bei der TM M2.
|
Mehrbändige und Nichtdeterministische TM
