|
|
Meine Frage:
Hallo,
Ich soll zeigen, dass eine 2-Dimensionale Turingmaschine äquivalent zur einfachen k-Band Turingmaschine ist und den Platz und Zeitverlust der Simulation berechnen.
Meine Ideen:
Ich hätte z.b.: alle x-Achsen der 2-Dimensionalen Turingmaschine als 1 Band der mehrdimensionalen TM gesehen.
--- Platzverlust wäre dann der freie Platz der Zweidimensionalen TM (In der 1Dimensionalen TM entstehen keine Löcher zwischen den Werten?!, was aber in der 2-dimensionalen Passieren kann
---- Zeitverlust: keiner?!
Danke schon mal für die Hilfe!
|
|
