Diskussion:Rekursiv aufzählbare Sprache

88.64.180.137 10:05, 24. Feb. 2007 (CET):

(in der Tat ist das Komplement des Halteproblems ein Spezialfall der Diagonalsprache und
    das Komplement der Diagonalsprache eine Erweiterung des Halteproblems).

Müsste der Satz nicht genau andersherum lauten: "In der Tat ist das Komplement des Halteproblems eine Erweiterung der Diagonalsprache und das Komplement der Diagonalsprache ein Spezialfall des Halteproblems". Denn es gilt:

K(Diagonalsprache) = K( {<M> | M akzeptiert <M> nicht} ) = {<M> | M akzeptiert <M>} = spezielles Halteproblem = Spezialfall des Halteproblems
K(Halteproblem) = K( {(<M>,w) | M akzeptiert w} ) = {(<M>,w) | M akzeptiert w nicht} =
    Erweiterung von {(<M>,<M>) | M akzeptiert <M> nicht } ~= Erweiterung der Diagonalsprache

Update: Ich habe nach gemeinsamen Durchdenken des Problems mit einem Komilitonen oben angedachte Änderung vorgenommen.

---

Mstigge 13:55, 11. Jan. 2008 (CET):

Die Diagonalsprache ist z.Zt. umdefiniert als das Komplement dessen, was ihr oben diskutiert. Ich fand diese Definition eingängiger da sie so die eigentliche Diagonal-Eigenschaft in den Mittelpunkt stellt. Das Nichtakzeptanz-Verhalten ist ja dann schon der nächste Schritt.

Damit ist das jetzt leider Inkonsistent mit dem Artikel Rekursiv_aufzählbare_Sprache. Einer muss angepasst werden, bitte um Meinungen.

Update:: Artikel Diagonalsprache wurde verändert und ist nun konsistent mit Rekursiv_aufzählbare_Sprache.

Sinn?

Hallo,

das ist mein erster Wikibeitrag, also entschuldigt bitte, wenn ich irgendwas falsch mache.

Die folgende Aussage ist so etwas Sinn frei. Denn logisch betrachtet ist es klar, dass es nur diese Aussagen gibt. Interessant wäre eher Folgerungen daraus.

Allgemein gilt für eine Sprache L und ihr Komplement K(L) stets genau eine der folgenden drei Eigenschaften:

• L und K(L) sind rekursiv (und somit auch rekursiv aufzählbar).
• L und K(L) sind nicht rekursiv aufzählbar.
• Genau eine der Sprachen L und K(L) ist rekursiv aufzählbar (aber nicht rekursiv), die andere ist nicht rekursiv aufzählbar.

Also eine Folgerund wäre z.B. dass L und K(L) rek. aufz. -> L ist entscheidbar. Oder auch L rek aufzählbar und K(L) nicht rek. aufz. -> L nicht entscheidbar.

Schöne Grüße Olli (nicht signierter Beitrag von 92.206.120.144 (Diskussion) 20:14, 13. Jul 2010 (CEST))

Ich habe mir erlaubt, deinen Beitrag etwas anders zu formatieren, ansonsten herzlich willkommen! So offensichtlich ist die Aussage aber nicht: Es könnte prinzipiell auch die Möglichkeit geben, dass L rekursiv ist und K(L) nicht rekursiv aufzählbar. Es ist also gut zu wissen, dass nur genau diese Korrelationen möglich sind. Es wäre tatsächlich gut, die Bedeutung der Eigenschaften zu nennen, aber deine Vorschläge sind etwas ungenau: Sind L und K(L) beide rek. aufz., so müssen sie gemäß der obigen Aussage sogar rekursiv sein. Dass eine rekursive Sprache entscheidbar ist, steht aber schon zu Beginn des Artikels. --Zahnradzacken 22:55, 13. Jul. 2010 (CEST)