Matroids Matheplanet Forum Index
Moderiert von Bilbo
Informatik » Theoretische Informatik » Akzeptanz des leeren Wortes
Autor
Kein bestimmter Bereich J Akzeptanz des leeren Wortes
kelvin
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 27.06.2003
Mitteilungen: 184
Wohnort: Niedersachsen
  Themenstart: 2004-03-29

Hi, Ich habe ein Problem mit dem Beweis, dass es keinen Algorithmus geben kann, der entscheidet, ob eine Turingmaschine das leere Wort akzeptiert. Bei uns wurde dieser Beweis mithilfe einer Reduktion des Akzeptanzproblems gefuehrt. Ich denke auch, dass ich soweit alles verstanden habe, aber ich bin mir nicht sicher, dass der Beweis wirklich korrekt ist. Hier der Beweis aus unserem Skript: Link Dabei ist Lacc die Sprache, die das Akzeptanzproblem loest. Mein Problem bei dem Beweis ist, dass ich nicht denke, dass die angegebene Koposition von Turingmaschinen tatsaechlich das Akzeptanzproblem loest. Letztendlich kann man doch fuer JEDES Wort w und fuer JEDE Turingmaschine M w auf das Band von M schreiben. Und wenn M dann das leere Wort akzeptiert, hat sie w auf ihrem Band stehen und hat dieses Wort dann akzeptiert. In dem Beweis wird, meiner Meinung nach, ueberhaupt keine Aussage darueber getroffen, dass w in der Sprache von M liegt! Das Akzeptanzproblem ist damit auch sicher nicht geloest. Mein Problem mit anderen Worten: Man kann ein Wort w und eine Turingmaschine M (die das leere Wort akzeptiert) waehlen, fuer die gilt, dass M w nicht akzeptiert. Fuer dieses Paar koennte man mit der in dem Beweis angegebenen Komposition von Turingmaschinen aber beweisen, dass M w akzeptiert. Offensichtlich ein Widerspruch! Waere super, wenn mir jemand erklaeren koennte, wo und ob ich da falsch liege. Mir ist klar, dass die Sprache nicht entscheidbar ist, das folgt ja schon aus dem Satz von Rice (nichttriviale Eingenschaft), aber ich kann leider das oben beschriebene Problem in dem Beweis so nicht akzeptieren. Vielen Dank schonmal! Gruß Kelvin [ Nachricht wurde editiert von kelvin am 2004-03-29 13:05 ]


   Profil
hirngeschwandter
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 14.10.2003
Mitteilungen: 1063
Wohnort: Darmstadt (z.Z. in Dresden)
  Beitrag No.1, eingetragen 2004-03-29

Hallo, evtl. verstehe ich Dich falsch aber m.M. würde Dein M bei so einem Verhalten _alle_ Wörter akzeptieren. Das Problem scheint doch zu sein, daß M überhaupt nicht nachschaut, ob noch Eingabesymbole vorliegen sondern unmittelbar am Anfang bereits akzeptiert. Nehmen wir mal den Extremfall - M akzeptiert nur das leere Wort. Eine solche TM müßte schon testen ob die Eingabe leer ist und genau dann akzeptieren. Gruss Enno [ Nachricht wurde editiert von hirngeschwandter am 2004-03-29 15:36 ]


   Profil
Plex_Inphinity
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 01.05.2002
Mitteilungen: 3601
  Beitrag No.2, eingetragen 2004-03-29

Hallo, Mir scheint du bringst da irgendwie M und M_w durcheinander. Beachte dass die TM M_w nicht die gleiche TM wie M ist, sondern eine etwas abgeänderte TM , die nur M auf dem Wort w simuliert. Vielleicht hilft es Dir, wenn ich den Beweis nochmal, so wie ich ihn verstanden habe wiedergebe. \ Annahme: L_\eps sei rekursiv. zu zeigen: Wenn L_\eps rekursiv ist , ist auch L_acc rekursive. (Widerspruch) Beweis: Man kann zu jeder Turingmaschine M und jedem Wort w aus dem Eingabealphabet eine Turingmaschine M_w konstruieren , die wie folgt arbeitet: M_w schreibt ungeachtet der Eingabe das Wort w auf sein Band und simuliert dann die Arbeit von M auf diesem Wort. Somit gilt: M_w akzeptiert jedes Wort(inklusive dem leeren Wort) genau denn, wenn M das Wort w akzeptiert, d.h. \epsilon \el L(M_w)  <=> w \el L(M)


   Profil
kelvin
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 27.06.2003
Mitteilungen: 184
Wohnort: Niedersachsen
  Beitrag No.3, vom Themenstarter, eingetragen 2004-03-29

Hi, erstmal vielen Dank fuer Eure Antworten Ihr Zwei! Schade, aber leider verstehe ich den entscheidenden Schritt immer noch nicht. Es ist klar, dass M und ein beliebiges Wort w zu Mw werden. Nun steht der Lesekopf der Maschine im Initialzustand q0 auf dem ersten Zeichen von w = s1...sn . Soweit einfach. Nun bekommt Mw keine Eingabe, also das leere Wort. Die Maschine akzeptiert also, wenn q0 auch final ist, denn der Kopf steht ja, nach Konstruktion, auf q0. Sorry, aber ich verstehe nun einfach nicht, wie das entscheidet, ob w von M akzeptiert wird. w kann doch beliebig gewaehlt werden. Meps akzeptiert c(M)w gdw Mw akzeptiert Epsilon. Das ist klar. Mw akzeptiert Epsilon gdw M akzeptiert w. Waere echt super, wenn Ihr das nochmal erklaeren koenntet. Was ist denn, wenn w nicht in der Sprache von M liegt, M aber das leere Wort akzeptiert. Dann haelt doch definitiv Mw auf das leere Wort als Eingabe in einem Finalzustand. Und dann ist doch auch w akzeptiert, obwohl es nicht aus der Sprache von M ist. Wo ist da mein Denkfehler? Viele Grueße Kelvin edit: O.K. ich habs verstanden. Ist schon klar, keine Eingabe ist ja die Eingabe w, die auf dem Band steht! Also wenn M Epsilon, oder w akzeptiert, wird Mw akzeptiert. Ferner ist die Frage, ob M Epsilon akzeptiert auch gar nicht wichtig, weil der Lesekopf nicht auf dem ersten Blank Symbol steht, sondern auf dem ersten Zeichen von w !!! So jetzt gehe ich mich erstmal schaemen ;) Vielen Dank nochmal. [ Nachricht wurde editiert von kelvin am 2004-03-29 19:27 ]


   Profil
hirngeschwandter
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 14.10.2003
Mitteilungen: 1063
Wohnort: Darmstadt (z.Z. in Dresden)
  Beitrag No.4, eingetragen 2004-03-29

Hallo, das hatte ich versucht zu erklären. In dem von Dir beschriebenen Szenario würde die Maschine _alle_ Wörter akzeptieren, denn sie begnügt sich ja offensichtlich damit, daß q0 akzeptierend ist, ohne weitere Betrachtung der Eingabe. Dein Denkfehler liegt darin, daß eine Maschine, die bestimmte Wörter nicht akzeptiert, auch die vorgesetzte Eingabe berücksichtigen muß. Gruss Enno PS: Ok ;-) [ Nachricht wurde editiert von hirngeschwandter am 2004-03-29 19:28 ]


   Profil
Plex_Inphinity
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 01.05.2002
Mitteilungen: 3601
  Beitrag No.5, eingetragen 2004-03-29

\ \ >Nun bekommt Mw keine Eingabe, also das leere Wort. Die Maschine >akzeptiert also, wenn q0 auch final ist, denn der Kopf steht ja, nach >Konstruktion, auf q0. Nein das stimmt nicht. Verwechsel Turingmaschinen nicht mit endlichen Automaten. Das leere Wort IST auch eine Eingabe. Deshalb bleibt der Kopf nicht einfach auf q0 stehen, sondern M_w fängt an zu arbeiten. Stell es dir so vor: Erst wird ein Eingabewort auf das Band der Turingmaschine geschrieben. Dann drückt man auf einen Knopf und die Turingmaschine fängt an zu arbeiten. (In den meisten Fällen wird sie nun erstmal das Eingabeband inspizieren) Wenn man das leere Wort auf das Eingabeband schreibt, meint man damit, dass man eben nichts auf das Band schreibt und dann den Knopf drückt. Die Turingmaschine startet also mit leerem Eingabeband. Nochmal von Anfang an: Wie arbeitet M_w? Erst wird irgendeine Eingabe auf das Eingabeband von M_w geschrieben, dann wird M_w gestartet. Als erstes löscht M_w die ganze Eingabe, da sie unwichtig ist und schreibt dann das Wort w auf die Eingabe. Dann simuliert M_w die Berechnung von M auf w. Wichtig ist hier nur, dass es zu jeder beliebigen Turingmaschine X und jedem Wort y, solch eine Turingmaschine X_y, die das leere Wort genau dann akzeptiert, wenn X das Wort y akzeptiert, gibt und dass man sie effektiv ,wie oben beschrieben, konstruieren kann. Wie kann man nun mit Hilfe dieser Turingmaschinen L_acc erkennen? Man konstruiert eine neue Turingmaschine M_acc, die wie folgt arbeitet: M_acc erhält als Eingabe ein Wort cod(M)w und soll nun entscheiden, ob M das Wort w akzeptiert. Mit Hilfe des Wortes cod(M)w konstruiert M_acc nun die Turingmaschine M_w (die ja, wie gezeigt existiert und konstruierbar ist) und schreibt die Kodierung cod(M_w) auf das Eingabeband. Da nach Voraussetzung eine Turingmaschine M_\eps existiert, die erkennen kann, ob M_w das leere Wort akzeptiert, kann M_acc nun M_\eps auf der Eingabe cod(M_w) simulieren und akzeptiert somit genau dann, wenn M_w das leere Wort akzeptiert , genau dann, wenn M das Wort w erkennt. >Was ist denn, wenn w nicht in der Sprache von M liegt, M aber das >leere Wort akzeptiert. Dann haelt doch definitiv Mw auf das leere Wort >als Eingabe in einem Finalzustand. Gehen wir den Algorithmus mal durch: M_acc bekommt als Eingabe cod(M)w. M_acc konstruiert daraufhin die entsprechende Turingmaschine M_w und übergibt die Kodierung cod(M_w) M_\eps als Eingabe. M_\eps überprüft ob M_w auf dem leeren Wort hält. Hält M_w auf dem leeren Wort? Gehen wir den Algorithmus von M_w durch. M_w bekommt das leere Wort als Eingabe. M_w löscht die Eingabe (obwohl nix draufsteht) und schreibt w auf das Eingabeband. Dann simuliert M_w die Berechnung von M auf w. M verwirft w , also verwirft auch M_w => M_w verwirft das leere Wort. =>Also verwirft auch M_\eps ihre Eingabe cod(M_w). =>Also verwirft auch M_acc ihre Eingabe cod(M)w [ Nachricht wurde editiert von Plex_Inphinity am 2004-03-29 20:27 ] [ Nachricht wurde editiert von Plex_Inphinity am 2004-03-29 20:29 ]


   Profil
kelvin
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 27.06.2003
Mitteilungen: 184
Wohnort: Niedersachsen
  Beitrag No.6, vom Themenstarter, eingetragen 2004-03-29

Hi nochmal, hatte oben den Threat noch editiert und geschrieben, dass ich es verstanden hatte. Sorry, kam wohl etwas spaet. Hast aber recht, ich hab das ganze tatsaechlich mit Automaten verwechselt. Also noch mal ein dickes, fettes Dankeschoen an Euch Beide! Gruß Kelvin


   Profil
kelvin hat die Antworten auf ihre/seine Frage gesehen.
Das Thema wurde von einem Senior oder Moderator abgehakt.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]