Zu dieser Karteikarte gibt es einen kompletten Satz an Karteikarten. Kostenlos!
21
Implementierung der universellen TM als 3-Band-TM
- Band 1: simuliert das Band der TM M
- Band 2: enthält die Gödelnummer von M
- Band 3: enthält den jeweils aktuellen Zustand von M
Initialisierung:
1.) Überprüfung ob Eingabe mit korrekter Göldenummer beginnt (sonst Fehlermeldung)
2.) kopiert <M> auf Band 2
3.) kopiert Binärkodierung des Anfangszustand auf Band 3
4.) kopiert w auf Band 1
5.) Kopf steht auf erstem Zeichen von w
Simulation eines Schritts:
-aktualisiert Inschrift auf Band 1
-bewegt Kopf auf Band 1
-verändert den auf Band 3 abgespeicherten Zustand
Laufzeit:
für Initialisierung O(1) bei konstant angesehener Kodierungslänge
-Laufzeit eines Schritts ist kosntant
=> U simuliert M mit konstantem Zeitverlust
=> wenn wir als 1-Band simulieren quadratischer Zeitverlust
=> konstanter Zeitverlust: wenn GN auf Spur 2 und Zustand auf Spur 3 mit dem Kopf der TM M mitführen(?)
- Band 2: enthält die Gödelnummer von M
- Band 3: enthält den jeweils aktuellen Zustand von M
Initialisierung:
1.) Überprüfung ob Eingabe mit korrekter Göldenummer beginnt (sonst Fehlermeldung)
2.) kopiert <M> auf Band 2
3.) kopiert Binärkodierung des Anfangszustand auf Band 3
4.) kopiert w auf Band 1
5.) Kopf steht auf erstem Zeichen von w
Simulation eines Schritts:
-aktualisiert Inschrift auf Band 1
-bewegt Kopf auf Band 1
-verändert den auf Band 3 abgespeicherten Zustand
Laufzeit:
für Initialisierung O(1) bei konstant angesehener Kodierungslänge
-Laufzeit eines Schritts ist kosntant
=> U simuliert M mit konstantem Zeitverlust
=> wenn wir als 1-Band simulieren quadratischer Zeitverlust
=> konstanter Zeitverlust: wenn GN auf Spur 2 und Zustand auf Spur 3 mit dem Kopf der TM M mitführen(?)
