Bin gerade bei F3 und frage mich in welchem Zusammenhang die folgenden Begriffe stehen: terminieren - halten - akzeptieren.

Ich weiß, dass eine TM, wenn sie akzeptiert, in einem Endzustand hält.

Aber, wenn sie hält, befindet sich die Turingmaschine dann auch in einem Endzustand?

Und was ist, wenn sie terminiert? Befindet sie sich dann in einem Endzustand?

Und überhaupt? Ich bin verwirrt…[img]http://www.fb18.de/gfx/28.gif[/img]

Terminieren und halten ist ganz genau das gleiche, nur ein bisschen anders: Terminieren bezieht sich auf eine Rechnung, halten auf eine TM. Eine TM hält, wenn sie nicht weiterarbeiten kann, da es im momentanen Zustand keine passende Transition für das nächste Zeichen im Eingabeband gibt. Es muss dabei kein Endzustand sein.

Wenn Du jetzt nicht mehr verwirrt bist und das Gefühl vermisst: Für's Akzeptieren kenne ich auch die Definition, dass eine TM eine Eingabe akzeptiert, wenn es eine Erfolgsrechnung für die Eingabe gibt. Eine Erfolgsrechnung ist dabei eine Rechnung, die beim Startzustand beginnt und beim Endzustand ankommt, auch wenn die TM noch weiterlaufen könnte.
Bei Deiner Definition würde man die TM hingegen laufen lassen, bis sie hält, und dann gucken, ob es ein Endzustand ist.
Man kann auch mit beiden Definitionen das selbe erreichen, aber die TMs für eine bestimmte Sprache können leicht unterschiedlich aussehen - richte Dich einfach nach dem, was in eurem Skript steht.

eine TM hält, wenn sie in einem Endzustand ist oder es keinen Folgezustand gibt.
eine TM akzeptiert, wenn sie in einem Endzustand hält.

Danke für die Antworten. Bin jetzt nicht mehr so verwirrt…[img]http://www.fb18.de/gfx/22.gif[/img]

eine TM hält, wenn sie in einem Endzustand ist oder es keinen Folgezustand gibt.
eine TM akzeptiert, wenn sie in einem Endzustand hält.

Das ist nicht in allen Büchern auf die gleiche Weise definiert!

im F3-Skript z.B.:
eine TM hält, wenn es keinen Folgezustand gibt.

eine TM akzeptiert das Eingabewort, wenn sie irgendwann einen Endzustand erreicht.
(dort muss Sie nicht halten, sondern darf sogar auch weiterlaufen, was das Akzeptieren aber nicht mehr rückgängig macht!!)

Mit dieser Definition können DTM und NTM gleichartig behandelt werden!

Bei Asteroth & Baier:
eine DTM hält, IMMER wenn sie in einem Endzustand ist [A&B S.38, insbes. Fußnote] oder wenn es keinen Folgezustand gibt. (das kann also auch für andere, als Endzustände der Fall sein!)

eine DTM akzeptiert das Eingabewort, wenn sie in einem Endzustand hält.

für NTM's ist das nicht dort nicht mehr so sauber definiert, d.h. ob es dort auch (wie in F3) akzeptierende Rechnungen gibt, die nicht zwangsweise halten, ist dort nur zu erahnen.

Ist es wirklich richtig, dass beide Definitionen des Akzeptierens für DTM äquivalent sind?
Ist denn nicht die Sprache, die eine DTM gem. A&B akzeptiert immer präfixfrei??
(nach einem zu akzeptierenden Präfix ist man im Endzustand und nix geht mehr, der Weg dorthin ist, da DTM, ohnehin eindeutig)
Wie akzeptiere ich so die Sprache (ab)*??

grübel, denk, grübel

Ist es wirklich richtig, dass beide Definitionen des Akzeptierens für DTM äquivalent sind?
Ist denn nicht die Sprache, die eine DTM gem. A&B akzeptiert immer präfixfrei??
(nach einem zu akzeptierenden Präfix ist man im Endzustand und nix geht mehr, der Weg dorthin ist, da DTM, ohnehin eindeutig)

Die DTM muss ja nicht (im Gegensatz zu DPDA und DFA) schon
akzeptieren, sobald sie einen Präfix gelesen hat, der zur
Sprache gehört.

(Edit: D.h. die Definitionen sind äquivalent:
Wenn man alle Kanten, die Endzustände verlassen,
entfernt, ändert man nichts an der Sprache (denn die DTM
akzeptiert ja, wenn sie akzeptiert, das ganze Eingabewort).)

Wie akzeptiere ich so die Sprache (ab)*??

Von links nach rechts durchlaufen, wie ein endlicher
Automat, und, wenn das Wort richtig war und Blank gelesen
wird, akzeptieren.

Von links nach rechts durchlaufen, wie ein endlicher
Automat, und, wenn das Wort richtig war und Blank gelesen
wird, akzeptieren.

Durch das weitere Symbol Blank, oder was auch immer, [ ] oder #, wird die Sprache quasi präfixfrei, denn ohne das "Wortendesymbol" geht es ja nicht.
Genaugenommen würde ja jetzt "w#" (bzw. "wBlank") akzeptiert.
A&B sind hier nicht so exakt, wie ich mir das wünschen würde!
Nur eben, bei DTM und NTM sind rechts von jeder Eingabe beliebig viele Blank (#, [ ]) Symbole, auf die stets zugegriffen werden kann, bzw. manchmal auch muss!
(Anders als beim endlichen Automaten, der (auch in A&B) mit dem letzten Symbol der dann akzeptierten Engabe in den Endzustand gelangt und aus diesem bei einer längeren Eingabe auch wieder heraus kann.)