Informatiker Board | Druckvorschau: Äquivalenzproblem für Typ-0-Sprachen

Geschrieben von floh1994 am 21.06.2013 um 14:22:

Ä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!

Geschrieben von Karlito am 22.06.2013 um 11:29:

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 $[latex]\mathcal{L}_1 = \mathcal{L}_2[/latex]$ entscheidbar, so muss es eine TM geben, welche das Leerheitsproblem $[latex](\mathcal{L}_1 \cap \overline{\mathcal{L}_2}) \cup (\overline{\mathcal{L}_1} \cap \mathcal{L}_2) = \emptyset[/latex]$ 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 $[latex]w \in \mathcal{L}[/latex]$ und $[latex]w \in \overline{\mathcal{L}}[/latex]$ bzw $[latex]w \notin \mathcal{L}[/latex]$ für alle [latex]w[/latex]

entscheidbar ist, dann ist $[latex]\mathcal{L}[/latex]$ 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

Geschrieben von floh1994 am 22.06.2013 um 13:06:

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 $[latex]\mathcal{L}_1 = \mathcal{L}_2[/latex]$ entscheidbar, so muss es eine TM geben, welche das Leerheitsproblem $[latex](\mathcal{L}_1 \cap \overline{\mathcal{L}_2}) \cup (\overline{\mathcal{L}_1} \cap \mathcal{L}_2) = \emptyset[/latex]$ 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 $[latex]w \in \mathcal{L}[/latex]$ und $[latex]w \in \overline{\mathcal{L}}[/latex]$ bzw $[latex]w \notin \mathcal{L}[/latex]$ für alle [latex]w[/latex]

entscheidbar ist, dann ist $[latex]\mathcal{L}[/latex]$ entscheidbar und das gilt im allgemeinen nicht für Typ0-Sprachen (lt. Halteproblem).

Warum muss, wenn die Entscheidbarkeit von $[latex](\mathcal{L}_1 \cap \overline{\mathcal{L}_2}) \cup (\overline{\mathcal{L}_1} \cap \mathcal{L}_2) = \emptyset[/latex]$ gilt, das Komplement auch entscheidbar sein?

Geschrieben von Karlito am 22.06.2013 um 13:38:

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 $[latex](\mathcal{L}_1 \cap \overline{\mathcal{L}_2}) \cup (\overline{\mathcal{L}_1} \cap \mathcal{L}_2) = \emptyset[/latex]$ 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 [latex]w[/latex]

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

Geschrieben von floh1994 am 22.06.2013 um 18:18:

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?