Startseite
 
 
Fragen
 
Suchen
 
Über Uns
 
 
Registrierung Kalender Mitgliederliste Teammitglieder Suche Häufig gestellte Fragen Zur Startseite

Informatiker Board » Themengebiete » Theoretische Informatik » Berechenbarkeits- und Komplexitätstheorie » Äquivalenzproblem für Typ-0-Sprachen » Hallo Gast [Anmelden|Registrieren]
Letzter Beitrag | Erster ungelesener Beitrag Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen
Neues Thema erstellen Antwort erstellen
Zum Ende der Seite springen Äquivalenzproblem für Typ-0-Sprachen
Autor
Beitrag « Vorheriges Thema | Nächstes Thema »
floh1994
Grünschnabel


Dabei seit: 21.06.2013
Beiträge: 3
Äquivalenzproblem für Typ-0-Sprachen Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen
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!

Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von floh1994: 21.06.2013 15:11.
21.06.2013 14:22 floh1994 ist offline Beiträge von floh1994 suchen Nehmen Sie floh1994 in Ihre Freundesliste auf
Karlito Karlito ist männlich
Kaiser


Dabei seit: 11.04.2011
Beiträge: 1.461
Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen
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
22.06.2013 11:29 Karlito ist offline E-Mail an Karlito senden Beiträge von Karlito suchen Nehmen Sie Karlito in Ihre Freundesliste auf
floh1994
Grünschnabel


Dabei seit: 21.06.2013
Beiträge: 3
Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen
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?

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von floh1994: 22.06.2013 13:06.
22.06.2013 13:06 floh1994 ist offline Beiträge von floh1994 suchen Nehmen Sie floh1994 in Ihre Freundesliste auf
Karlito Karlito ist männlich
Kaiser


Dabei seit: 11.04.2011
Beiträge: 1.461
Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen
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
22.06.2013 13:38 Karlito ist offline E-Mail an Karlito senden Beiträge von Karlito suchen Nehmen Sie Karlito in Ihre Freundesliste auf
floh1994
Grünschnabel


Dabei seit: 21.06.2013
Beiträge: 3
Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen
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 floh1994 ist offline Beiträge von floh1994 suchen Nehmen Sie floh1994 in Ihre Freundesliste auf
Baumstruktur | Brettstruktur
Gehe zu:
Neues Thema erstellen Antwort erstellen
Informatiker Board » Themengebiete » Theoretische Informatik » Berechenbarkeits- und Komplexitätstheorie » Äquivalenzproblem für Typ-0-Sprachen

© by Informatikerboard.de
Forensoftware: Burning Board, entwickelt von WoltLab GmbH

 
© 2005-2020 bei Informatikerboard.de | Archiv, alt, neueste | Kontakt | Jugendschutz | Nutzungsbedingungen