Diskussion:Diagonalsprache

aus Wikipedia, der freien Enzyklopädie
Letzter Kommentar: vor 8 Jahren von Tormate in Abschnitt Zum Beweis D ist nicht semi-entscheidbar.
Zur Navigation springen Zur Suche springen

Habe den Artikel mal etwas überarbeitet, da wahren einige fachliche Unklarheiten drin. Vielleicht hört diese unsägliche Löschdiskussion ja auch mal auf.

Bezüglich der QA-Diskussion möchte ich dringend empfehlen, das Formale nicht aufzuweichen.

-- Mstigge 15:54, 13. Jan. 2008 (CET)Beantworten

Ich habe Deine Überarbeitungen gerade mal durchgeschaut und dabei ist mir aufgefallen, das in meinem Buch das ich als Quelle benutzt habe (Theoretische Informatik - eine algorithmenorientierte Einführung von Wegener) ist die Dieagonalsprache genau andersherum definiert. Dort steht, dass Sie als "Menge aller Wörter , so daß das Wort nicht akzeptiert" definiert ist.
Zur Semi-Entscheidbarkeit wäre es schön, wenn du dazu den Beweis schreiben könntest, da ich dazu nichts gefunden habe. Meiner Meinung nach ist das auch falsch, da ja nicht für alle Wörter entschieden werden kann ob Sie enthalten sind.
--Pizzamaka 20:56, 13. Jan. 2008 (CET)Beantworten
Ok, wenn das in früherer Literatur so definiert ist, sollte man da besser nichts durcheinander werfen. Kurze Google-Suche brachte auch nur die Definition "andersrum" zutage, daher sollten wir das hier wohl auch besser wieder umkehren und ich entschuldige mich für die Verwirrung.
Was die Semi-Entscheidbarkeit angeht, so ist die Sache einfach: Für ein gegebenes kann ja einfach auf Eingabe laufen gelassen werden. Sollte es zum Akzeptieren kommen, akzeptiert man. Positive Eingaben werden damit akzeptiert, negative (also ) nicht. Für positive Eingaben wird die Zugehörigkeit also entschieden. In die umgekehrte Richtung geht das nicht, aber daher heißt das ja auch semi-entscheidbar.
-- Mstigge 23:15, 13. Jan. 2008 (CET)Beantworten
Habe den Artikel nun umgeschrieben, damit er konsistent ist mit der Wegener-Definition. Direkt aus dem Wegener abschreiben ist aus urheberrechtlichen Gründen keine gute Idee. Außerdem finde ich diese ganzen - und -Indizes unübersichtlich, die braucht man nicht.
Die Semi-Entscheidbarkeit des Komplements habe ich nun auch in einen Absatz am Ende gegossen.
-- Mstigge 11:10, 14. Jan. 2008 (CET)Beantworten
Gute Bearbeitung. Mal schauen ob ich da noch was lernen kann und demnächst Artikel schreibe die nicht direkt so einen Flame auslösen. Ich denke mal, dass man den Artikel fürs erste so lassen kann.
--Pizzamaka 10:17, 15. Jan. 2008 (CET)Beantworten
Die "Flames" kamen ja nur durch so Nasen die ohne jegliche Ahnung wichtige Worte kundtun wollten. Also keine Sorge und weitermachen!
--Mstigge 14:06, 15. Jan. 2008 (CET)Beantworten

Komplement der Diagonalsprache

[Quelltext bearbeiten]

Im Artikel steht, dass das Komplement der Diagonalsprache das Halteproblem sein soll. Sind die Probleme nicht aber wie folgt definiert?

In Hopcroft et al. "Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie" wird das Komplement von D als "Universelle Sprache" bezeichnet und das Halteproblem (nach Alan Turing) ist die Frage ob "M bei gegebener Eingabe w anhält, unabhängig davon, ob M w akzeptiert" (Hopcroft, S. 389).

In Blum "Einführung in Formale Sprachen..." steht:

So wie ich das verstehe ist

--Comastalker 19:41, 4. Aug. 2009 (CEST)Beantworten

Der Artikel spricht vom "speziellen Halteproblem" K als Komplement von D. Das ist der Spezialfall von dem von dir definierten H in dem w die Kodierung von M ist. Selbst dieser Spezialfall ist nicht entscheidbar. Ich sehe, dass an einer zweiten Stelle im Artikel "speziell" fehlt, das ändere ich mal eben. --Mstigge 14:01, 28. Mai 2010 (CEST)Beantworten

Das Komplement der Sprache D = < w ist Goedelnummer und die zugehoerige Turingmaschine akzeptiert w nicht > ist auch nicht wie im Artikel angeben die Sprache < w ist Goedelnummer und die zugehoerige Turingmaschine akzepiert w > sondern < w ist keine Goedelnummer oder w ist Goedelnummer und die zugehoerige Turingmaschine akzeptiert w >. 79.193.66.23 19:41, 7. Okt. 2009 (CEST)Beantworten

Der Artikel behauptet nicht, dass w Gödelnummer sein muss. Ist w keine Gödelnummer, so kann man eine beliebige feste Turingmaschine zuordnen. Damit kann dann auch direkt und etwas eleganter vom Komplement gesprochen werden. Daher halte ich das für unproblematisch. --Mstigge 14:01, 28. Mai 2010 (CEST)Beantworten

Zum Beweis D ist nicht semi-entscheidbar.

[Quelltext bearbeiten]

So wie es jetzt da steht kann man denke ich nur Unentscheidbarkeit zeigen. Im Fall 2 kann man die Folgerung aus " darf nicht akzeptieren" nicht machen. Da hier terminiert implizit für den nächsten schritt angenommen worden ist.

Wir solten Entscheidbarkeit annehmen und können so Unentscheidbarkeit zeigen. Zusammen mit der semi-Entscheidbarkeit von Komplement folgt dann, dass nicht semi-entscheidbar ist. (nicht signierter Beitrag von Tormate (Diskussion | Beiträge) 18:28, 26. Feb. 2016 (CET))Beantworten