Hallo!

Ich habe scheinbar bisher immer etwas missverstanden, was das Akzeptieren eines Wortes angeht. Ich dachte, man lässt die Turingmaschine so lange laufen, bis sie hält, und guckt dann, ob sie in einem Endzustand gehalten hat.
Nach den Definitionen von Erfolgsrechnung (eine Rechnung, die zu einem Endzustand führt; egal, ob's danach noch weitergeht) und akzeptierte Sprache (alle Wörter, für die es eine Erfolgsrechnung gibt) ist ein Wort aber sofort akzeptiert, wenn die TM bei einem Endzustand vorbeikommt. Transitionen von einem Endzustand weg wären damit sinnlos.

Konkrete Frage, die sich daraus ergibt: Würde die folgende Maschine das Wort aa akzeptieren? Würde sie halten?
[img]http://f0k.de/pub/turing_aa.png[/img]
Ich hätte bisher gedacht, sie verliert sich dann ja in einer Endlosschleife über den Zustand q_2, akzeptiert das Wort also nicht. Nach dem, was ich jetzt gelesen habe, denke ich, sie würde es akzeptieren. Hält sie dann im Endzustand einfach an?

Soweit ich das verstanden habe, akzeptiert eine TM eine Sprache, wenn sie bei Eingabe eines jede Wortes aus der Sprache nach endlich vielen Schritten in einen der definierten Endzustände gelangt.

Und da sie das ja schon beim Lesen des ersten a's tut, sollte die das Wort akzeptieren, wenn ich nicht irre.
Da es ja ihre "Aufgabe" ist, in einen Endzustand zu kommen, sollte sie da wohl auch anhalten.

So wie tilo habe ich es auch verstanden.
Die Maschine müsste dann alle Worte die mit a beginnen akzeptieren, wenn ich mich nicht irre.

Hmm, ich hab mal im Skript nachgesehen, um jetzt die Definition
für die akzeptierte Sprache zu zitieren, aber habe keine gefunden
(ist da wirklich keine? Wo hast du deine her?)

Normalerweise schreibt man
[img]http://mokrates.de/cgi-bin/texstring?L(%5Cmathcal%7BT%7D)%3D%5C%7Bw%5Cin%5CSigma%5E*%5Cmid%20%5Cexists%20q%5Cin%20F%2Cu%2Cv%5Cin%5CGamma%5E*%3A%20q_0w%5Cvdash%5E*_%7B%5Cmathcal%7BT%7D%7D%20uqv%5C%7D[/img],
wenn [img]http://mokrates.de/cgi-bin/texstring?%5Cmathcal%7BT%7D%3D(Q%2C%5CSigma%2C%5CGamma%2C%20%5Cdelta%2C%20q_0%2C%5Csquare%2CF)[/img]
(wobei das [img]http://mokrates.de/cgi-bin/texstring?%5Cvdash[/img] den Konfigurationsübergang bezeichnet).

Insofern werden auch Wörter akzeptiert, bei deren Vorlage die
TM in einen Endzustand kommt und hinterher weiterrechnet.

Was deine Grafik angeht: Was bedeutet das S? Steht es für
"stop", also das was "N" im Skript bedeutet? Falls ja, dann
akzeptiert sie, weil es ja eine Rechnung gibt, die in einen
Endzustand führt.

Da es ja ihre "Aufgabe" ist, in einen Endzustand zu kommen, sollte sie da wohl auch anhalten.

Nein, das muss sie nicht, es kann dann auch noch
Folgekonfigurationen geben. Aber das ist eigentlich
nicht so wichtig, denn wenn du z.B. eine TM simulierst,
kannst du nach Erreichen eines Endzustands die Simulation
abbrechen, du kennst das Ergebnis ja schon.

Man kann's auch so formulieren: wenn man bei TMs alle von
Endzuständen wegführenden Pfeile entfernt, ändert man nichts
an der akzeptierten Sprache. Insofern kann man meistens
davon ausgehen, dass die TM nur bis zum Endzustand rechnet
(aber formal nach Definition muss sie das nicht).

Hmm, ich hab mal im Skript nachgesehen, um jetzt die Definition für die akzeptierte Sprache zu zitieren, aber habe keine gefunden (ist da wirklich keine? Wo hast du deine her?)

Sorry… nein, für deterministische Automaten ist nichts definiert, aber für nichtdeterministische steht's in 18[ 15 ].

Was deine Grafik angeht: Was bedeutet das S? Steht es für
"stop", also das was "N" im Skript bedeutet?

Ja, das ist die Bezeichnung in JFlap, was uns in der Vorlesung empfohlen wurde (ein empfehlenswertes Programm zum Bauen und Testen von endlichen Automaten, Turingmaschinen, Kellerautomaten, Grammatiken…).

OK, also eine Maschine kann ein Wort akzeptieren, ohne zu halten? Das heißt, das Halteproblem beinhaltet nicht solche <A><w>, bei denen die Maschine A die Eingabe w zwar akzeptiert, aber nicht hält?

Irgendwie scheint "halten" und "akzeptieren" manchmal im Script oder in Musterlösungen synonym verwendet zu werden, zumindest wird immer davon ausgegangen: "akzeptierten" impliziert "halten".
Hoffe, das gibt in der Klausur keine Doppeldeutigkeiten deshalb.

Wenn eine Turingmaschine akzeptiert, so akzeptiert sie stets die ganze endliche Bandinschrift. Auch wenn sie diese nicht vollständig bearbeitet hat.
So war es zumindest in F3.
Also würde Sie bei Dir oben das Wort aa auch akzeptieren.

Hmm, ich hab mal im Skript nachgesehen, um jetzt die Definition für die akzeptierte Sprache zu zitieren, aber habe keine gefunden (ist da wirklich keine? Wo hast du deine her?)

Sorry… nein, für deterministische Automaten ist nichts definiert, aber für nichtdeterministische steht's in 18[ 15 ].

OK, die Definition gilt dann auch für die deterministischen,
weil die deterministischen ja auch nichtdeterministische sind.
Früher wurde das auch andersrum erklärt: erst NTM mit obiger
Definition und dann DTMs als solche NTMs, bei denen jede
Konfiguration höchstens eine Nachfolgekonfiguration hat.

OK, also eine Maschine kann ein Wort akzeptieren, ohne zu halten? Das heißt, das Halteproblem beinhaltet nicht solche <A><w>, bei denen die Maschine A die Eingabe w zwar akzeptiert, aber nicht hält?

Streng genommen: ja. Aber das Problem, ob eine gegebene TM ein
gegebenes Wort akzeptiert, ist äquivalent (im Sinne von wechsel-
seitiger Reduzierbarkeit) zu der Frage, ob die TM bei Eingabe
des Wortes anhält oder nicht.

Irgendwie scheint "halten" und "akzeptieren" manchmal im Script oder in Musterlösungen synonym verwendet zu werden, zumindest wird immer davon ausgegangen: "akzeptierten" impliziert "halten".
Hoffe, das gibt in der Klausur keine Doppeldeutigkeiten deshalb.

Ja, das wird in vielen Büchern auch nicht so auseinandergehalten.
Das liegt wohl daran, dass man zu einer TM A leicht eine andere
konstruieren kann, die hält gdw. A akzeptiert. (Und umgekehrt
genauso.) Da es in der Theorie fast nie (außer in Beispielen)
darum geht, eine konkrete TM irgendwie zu beurteilen, sondern eher
um Algorithmen o.ä., die das tun, unterscheiden sich die
Eigenschaften "Akzeptieren" und "Halten" nicht nennenswert.

IIRC wird bei Hopcroft/Ulman immerhin noch erwähnt, dass ab
sofort "OE" alle TM nach dem Akzeptieren halten.