Äquivalenzproblem für Typ-0-Sprachen |
21.06.2013, 14:22 | Auf diesen Beitrag antworten » | ||||
floh1994 | Äquivalenzproblem für Typ-0-Sprachen Hallo! Ich möchte mithilfe des Halteproblems zeigen, dass das Äquivalenzproblem nicht entscheidbar ist. Dazu folgender Ansatz: Annahme: Ä. ist entscheidbar. Dann gibt es eine universelle TM M, die die folgenden (nicht rekursiv-aufzählbaren) Sprachen L1 und L2 auf Äquivalenz entscheiden könnte: L1 = L2 = {<M> | M ist TM und hält für keine Eingabe} Da aber L1 und L2 für keine Eingabe halten, dann wird auch die universelle TM M nicht halten. Ist meine Idee korrekt? Danke schon mal im vorraus fürs Antworten! |
||||
|
|||||
22.06.2013, 11:29 | Auf diesen Beitrag antworten » | ||||
Karlito | Hallo, ich denke dein Ansatz ist nicht korrekt. Du kannst nicht einfach eine TM hernehmen, die nich anhält. Ich bin ein wenig raus aus dem Thema, aber denk mal über folgende Argumentation nach: Sei entscheidbar, so muss es eine TM geben, welche das Leerheitsproblem entscheidet (Quelle: Wikipedia). Unabhängig davon ob die Vereinigung oder der Durchschnitt von Typ0-Sprachen entscheidbar ist, müsste das Komplement einer beliebigen Typ0 Sprache entscheidbar sein. Wenn jedoch und bzw für alle entscheidbar ist, dann ist entscheidbar und das gilt im allgemeinen nicht für Typ0-Sprachen (lt. Halteproblem). Ich hoffe meine formulierung ist nicht zu ungenau. Ich denke die Idee sollte verständlich sein. VG, Karlito |
||||
22.06.2013, 13:06 | Auf diesen Beitrag antworten » | ||||
floh1994 |
Kannst du mir erklären, warum ich das nicht darf? Meine Überlegung war, dass wenn ich einfach 2 konkrete gleiche Sprachen auf Äquivalenz teste, und bei Gleichheits- oder Ungleichheitsfall einen Widerspruch erzeugen kann, dass dann das Ä.-Problem nicht entscheidbar ist. Wenn man etwas widerlegen möchte, reicht es doch, wenn man ein Gegenbeispiel findet, oder?
Warum muss, wenn die Entscheidbarkeit von gilt, das Komplement auch entscheidbar sein? |
||||
22.06.2013, 13:38 | Auf diesen Beitrag antworten » | ||||
Karlito | Hallo,
Naja, Typ0-Sprachen sind doch rekursiv aufzählbare Sprachen. Somit ist doch schon die vorraussetzung falsch. Wenn Du nur nicht rekurisiv aufzählbare Sprachen betrachtest, geht das ja am Ziel vorbei... (s. Wikipedia)
Naja, weil du nachweisen musst, dass es Wörter gibt, die in einer Sprache enthalten sind und in der anderen nicht... Und dass ein Wort in einer Sprache nicht enthalten ist, ist das Komplementproblem. D.h. hält eine Turingmaschine bei einem Wort nicht an. Ich glaube man muss noch zusätzlich den Satz von Rice mit heranziehen, um von allgemeinen Halteproblem auf dieses spezielle zu schließen... VG, Karlito |
||||
Anzeige | |||||
|
|||||
22.06.2013, 18:18 | Auf diesen Beitrag antworten » | ||||
floh1994 |
Dass Typ0-Sprachen immer rekursiv aufzählbar sind hab ich nicht gewusst. Kannn man dann vielleicht über das allgemeine Halteproblem (ist rekursiv aufzählbar) argumentieren? Also L1 = L2 = {<M>x | M ist TM und hält gestartet mit x} Dann kann man ja die Nicht-Entscheidbarkeit des Ä.-Problems über das Komplement zeigen, welches ja nicht rekursiv-aufzählbar ist. Ginge das so? |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|