Diskussion:Diagonalsprache

Die Löschung der Seite „Diagonalsprache“ wurde ab dem 9. Januar 2008 diskutiert und abgelehnt. Für einen erneuten Löschantrag müssen gemäVorlage:SS den Löschregeln neue Argumente vorgebracht werden.

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)

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 $w_{i}$, so daß $M_{i}$ das Wort $w_{i}$ 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)

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 $w$ kann ja $M_{w}$ einfach auf Eingabe $w$ laufen gelassen werden. Sollte es zum Akzeptieren kommen, akzeptiert man. Positive Eingaben $w\in D$ werden damit akzeptiert, negative (also $w\notin D$) 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)

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 $i$- und $j$-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)

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)

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)

Komplement der Diagonalsprache

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

${\overline {D}}:=\{w\mid M_{w}~{\text{akzeptiert w}}\}$

$H:=\{Mw\mid M~{\text{haelt auf}}~w\}$

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:

$H:=\{x\in \{0,1,\#\}^{*}\mid x=<M><w>~{\text{fuer eine Turingmaschine M, die auf Eingabe w haelt}}\}$

So wie ich das verstehe ist $H\neq {\overline {D}}$

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

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)

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)

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)

Zum Beweis D ist nicht semi-entscheidbar.

So wie es jetzt da steht kann man denke ich nur Unentscheidbarkeit zeigen. Im Fall 2 $w\notin D$ kann man die Folgerung aus "$M_{w}$ darf $w$ nicht akzeptieren" nicht machen. Da hier $M$ 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 $D$ Komplement folgt dann, dass $D$ nicht semi-entscheidbar ist. (nicht signierter Beitrag von Tormate (Diskussion | Beiträge) 18:28, 26. Feb. 2016 (CET))