 2-Dimensionale Turing Maschine |
cpblue
Grünschnabel
Dabei seit: 17.05.2011
Beiträge: 1
 |
|
| 2-Dimensionale Turing Maschine |
     |
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!
|
|
17.05.2011 15:06 |
|
|
Karlito 
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Hi,
ich bin selbst noch zu wenig im Stoff um gute Antworten zu liefern. Hier trotzdem ein paar weitere Ideen:
Keine Ahnung, ob das mit der Variante ein Band für jede X-Achse geht... Könnte Fragen aufwerfen. Weil wo kontroliest du welches Band an welcher Stelle gerade ist (Art Adressierung).
Vlt ist es hier günstig, die Bänder zu diagonalisieren http://de.wikipedia.org/wiki/Cantors_erstes_Diagonalargument. Hier Spiralen laufen, wenn negative Koordinaten möglich sind...
So bräuchtest du auf einem weiterem Band nur den Coder welcher die 2Dim-TM simuliert...
Platz dürfte der selbe sein (+ simulations-Code = konstant, dafür würde ich auch meine Hand nicht ins Feuer legen), da du ne Bijektive Abbildung von 2Dim auf 1Dim erstellst.
Zeitaufwand tippe ich auf polynomiell, ohne Beweis... Wie gesagt, ich stehe noch zu wenig im Stoff...
MfG,
Karlito
|
|
|
19.05.2011 01:17 |
|
|
|
