Äquivalenzproblem für Typ-0-Sprachen |
floh1994
Grünschnabel
Dabei seit: 21.06.2013
Beiträge: 3
|
|
|
21.06.2013 14:22 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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 11:29 |
|
|
floh1994
Grünschnabel
Dabei seit: 21.06.2013
Beiträge: 3
|
|
Zitat: |
Original von Karlito
ich denke dein Ansatz ist nicht korrekt. Du kannst nicht einfach eine TM hernehmen, die nich anhält. |
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?
Zitat: |
Original von Karlito
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).
|
Warum muss, wenn die Entscheidbarkeit von gilt, das Komplement auch entscheidbar sein?
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von floh1994: 22.06.2013 13:06.
|
|
22.06.2013 13:06 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Hallo,
Zitat: |
Original von 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?
|
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)
Zitat: |
Original von floh1994
Warum muss, wenn die Entscheidbarkeit von gilt, das Komplement auch entscheidbar sein?
|
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
|
|
22.06.2013 13:38 |
|
|
floh1994
Grünschnabel
Dabei seit: 21.06.2013
Beiträge: 3
|
|
Zitat: |
Original von Karlito
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) |
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?
|
|
22.06.2013 18:18 |
|
|
|