Hi!
wer kann mir kurz und knapp erklären, wie eine DTM eine NTM simuliert???
Vielen Dank!
Spontane Idee:
Man kann die Entscheidungsmoeglichkeiten, die eine NTM im Laufe eines Programmablaufs hat, als (moeglicherweise unendlichen) Baum darstellen. Die Hoehe entspricht der Anzahl der Programmschritte bis zu dem Punkt, jede Verzweigung einer Entscheidung.
Die Simulation einer NTM durch eine DTM koennte man dann als Breitensuche in diesem Baum realisieren.
Hey.
also ist das quasi eine Simulation durch eine DTM und keine Transformation oder verstehe ich das falsch?
Achso, Du meinst mechanische Transformation im Sinne von "nimm diese und jene Kante im Zustandsuebergangsdiagramm weg und fuege diese und jene Kante ein"? Ich glaub, so einfach gehts nicht.
genau das meinte ich!!!
also wenn ich das richtig verstanden habe, handelt es sich um eine Simulation! Das heißt, die NTm wird wohl kodiert der DTM übergeben werden müssen, ja!?!
Nein. Wozu?
Du codierst das Wissen ueber die NTM in die DTM das ist alles. Sie wird mehr Zustaende haben (und mehr Zuege brauchen) als die NTM, aber sie wird die gleichen Woerter wie die NTM als Eingabe haben (und die gleiche Teilmenge dieser Woerter akzeptieren). (Wuerdest du die NTM codiert als Eingabe haben, haettest du ueberhaupt keine Aequivalenz der akzeptierten Sprachen!!)
(Dies als Breitensuche zu machen (siehe UncleOwen's Kommentar unten) ist wichtig, damit sicher gestellt ist, dass die DTM auch wirklich in einen Endzustand geraet, wenn die NTM dies tut (bei einer Tiefensuche waere dies nicht umbedingt der Fall).)
Cheers.
P.S. Fuer Beweise (mit huebschen Bildchen [img]
http://www.fb18.de/gfx/28.gif[/img]) guck einfach mal in eines der Buecher zur Theoretischen Informatik. In den meisten steht das sehr gut drin - und meist auch gar nicht soo umfangreich. H&U schreiben ca. 1 Seite. – Musst dich also nicht durch einen 5-10 Seiten Beweis hangeln [img]
http://www.fb18.de/gfx/25.gif[/img]
achso!
ich verstehe nur noch nicht, wie man das Wissen über die NTM in die DTM kodiert? Bzw. wie sollte man die Breitensuche implementieren? Gibt's da ein ganz simples und kurzes Beispiel an dem man das erklären könnte! Leider verstehe ich bei den Büchern und Skripten zu wenig! Der Beweis ist ja auch im F3-Skript.. aber das raff ich da leider nicht!!!
Bitte also noch einmal um Hilfe!!!
Danke!!!
Ein kleiner Ruecksprung zu F2: Bei der Konstruktion eines DFA zu einem NFA (Potenzautomat) codiert man auch das "Wissen" des NFA in den DFA - die Zustaende des DFA sind gerade die Mengen all jener Zustaende in denen der NFA sich befinden koennte (bzw. in denen sich seine mehreren Kontrollen befinden, je nach benutzter Vorstellung).
Und hin zu F3: Bei der Konstruktion der DTM zu einer NTM "kodiert" man ebenso das Wissen der NTM (d.h. die Konfiguration in der sie sein koennte) in die DTM. Nur ist es hier komplizierter und daher wirst du in den Buechern meist auch nicht (wie beim Potenzautomaten) eine exakte Konstruktion finden - die auch gar nicht noetig ist, da man ja bspw. weiss, dass man sowas machen kann wie ein Wort mehrmals hintereinander zu schreiben o.ae. auch ohne, dass man nun hierfuer alle noetigen Zustaende und Uebergaenge exakt definieren muesste.
Man hat also die Idee und sagt dann welche Arbeitsschritte die DTM nacheinander ausfuehrt - ohne dass man hierfuer explizit alle noetigen Zustaende und Uebergaenge angibt - dann muss man noch zeigen, dass wirklich die akzeptierten Sprachen gleich sind. (Bei fast allen Beweisen mit Turing Maschinen geht man so vor, bspw. auch wenn du zeigen willst das Ein-Band und Mehr-Band Turing Maschinen gleich maechtig sind, oder 1-d-Band und 2-d-Band TM usw.)
Cheers.
P.S. Der Beweis im Skript ist vielleicht etwas schwierig formuliert, ich habe ihn auch zuerst nicht verstanden, aber die Idee (die Konfigurationen, die die NTM durchlaeuft bilden einen Baum, den man durchsuchen kann (in der Breite)) kam rueber und nach etlichen Bananen und ein paar Kannen Kamilientee hat's dann doch geklappt – kriegst du auch hin [img]
http://www.fb18.de/gfx/25.gif[/img]
P.P.S. Oder wolltest du die Idee (und die einzelnen Arbeitsschritte der DTM) genauer wissen?
