---

Geschrieben von cpblue am 17.05.2011 um 15:06:

  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!

---

Geschrieben von Karlito am 19.05.2011 um 01:17:

 

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