2-Dimensionale Turing Maschine |
| 17.05.2011, 15:06 | Auf diesen Beitrag antworten » |
| cpblue | 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! |
|
|
|
| 19.05.2011, 01:17 | Auf diesen Beitrag antworten » |
| Karlito | 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 |
|
|