Entscheidbarkeit des leeren Wo < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | Sei [mm] E=\{w|\varepsilon \in Def(v(w))\}. [/mm] Zeigen Sie: E ist nicht entscheidbar, d.h. es gibt kein allgemeines Verfahren, mit dem getestet werden kann, ob eine TuringMaschine (TM) das leere Wort akzeptiert. |
Hallo liebe Alle 
Ich habe oben genannte Aufgabe gestellt bekommen. Nun bin ich schon eine geraume Weile auf der Suche nach der Lösung. Ich nehme an, dass das Ganze etwas mit dem Halteproblem zu tun hat.
Wenn man also [mm] \varepsilon [/mm] als Eingabe in eine TM1 eingibt, dann stoppt die TM1, falls das Wort zur Sprache gehört, oder eben nicht, falls es nicht dazu gehört.
Wenn man nun also eine TM2 konstruieren möchte, die die TM1 als Eingabe erhält und überprüfen soll, ob E zur Sprache von TM1 gehört, dann läuft die Maschine unendlich weiter.
Ist dies tatsächlich die Antwort auf die oben gestellte Frage, oder habe ich da einen Denkfehler?
Vielen Dank für Eure Hilfe.
Liebe Grüße
G.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:20 Mi 28.01.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
