Hi,
kann mir jemand erklären wie ich eine TM in einer RAM simulieren kann, und das ganze nochmal anders rum? Im Skript steht leider nicht viel dazu.
Und wenn wir schonmal dabei sind, wie simuliere ich mit einem DFA eine NFA?
SilentK
ups habe mich verschrieben.
Wollte eigentlich fragen wie man eine NTM mit einer DTM simuliert.
SilentK
Hi Leute,
will denn keiner Antworten? Habt ihr wenigstens einen guten Literaturhinweis für mich? In den Büchern in den ich nachgeschaut habe, finde ich auch nichts !
SilentK
Die Erklärung aus welchem Skript liegt dir da eigentlich Zugrunde? Mir ist gar nicht mehr in Erinnerung, das RAMs im Grundstudium schon mal besprochen wurden. Wenn doch, könnte ich noch mal die Simulationsgeschichte aus dem AUK Skript aufschreiben.
Doch, RAMs und TMs kamen in F3 vor.
Kamen im F3 Skript vor, aber dort steht nur was über die Komplexität.
Meine Antwort auf die Frage "Kann denn die RAM dasselbe wie die TM" war heute "Eine TM kann von einer RAM simuliert werden und umgekehrt", nach mehr hat er (Farwer) nicht gefragt.
Auf den alten Folien vom WS 2001 stehen auch nur die Komplexitäten, und dass man einem TM durch ein RAM simulieren kann, indem man pro Bandzeile ein Register benutzt und bei der Simulation einer RAM durch eine TM die Register hintereinander auf das Band schreiben muss.
Edit: Zur Simulation einer NTM durch eine DTM habe ich folgendes auf den Folien gefunden:
- Eine DTM hat keine Platzbeschränkung
- Der Konfigurationsbaum muss auf dem Band gemerkt werden
- es muss eine systematische Suche nach einer Erfolgsrechnung erfolgen.
Ich wurde richtig ausgefragt zum Thema gegenseitige Simulation von RAMs und TMs, der nötige Aufwand dafür, die Mächtigkeit und sowas, und hatte keine Ahnung…
Hab herumgedruckst, aber im Skript stand sowas nicht.
Genau dass ist auch mein Problem, es steht nicht im Skript drinne, aber ich bin mir irgendwie sicher das ich in meiner Prüfung danach gefragt werde .
Naja ich gebe mich dann erstmal mit den zwei Theoremen im F3 Skript zu frieden.
Wenn jemand mehr wissen sollte, kann er es ja gerne noch schreiben, würde mich sehr darüber freuen.
SilentK
will denn keiner Antworten? Habt ihr wenigstens einen guten Literaturhinweis für mich? In den Büchern in den ich nachgeschaut habe, finde ich auch nichts !
Die Simultation einer RAM durch eine TM wird teilweise beschrieben in "Komplexitätstheorie, Band 1: Grundlagen" von
K. Rüdiger Reischuk, S.76. Allerdings wird dort die Simulation konkreter Befehle nur anhand der Beispiele READ(V) und ADD demonstriert. Außerdem wird beschrieben, wie die Register auf dem Band gespeicher werden und erklärt, wie die T*S Zeitbeschränkung zustande kommt.
tschüs
Georg
