Moin …

kann mir nochmal jemand kurz sagen, welche Mengen RE und REC sind? RE ist recursively enumerable …also die Menge der semi-entscheidbaren Mengen. Und REC? Sind das die entscheidbaren? Das steht nicht im AUK Skript und auch nicht im Schöning … ich weiß nur, dass REC wohl für recursive steht … könnte also was mit Berechenbarkeit der charakteristischen Funktion zu tun haben, aber sicher bin ich mir da nicht. Danke!

Ich weiss nicht, ob dir das jetzt hilft, aber das kam schon bei F3 dran.

Rec ist wie du schon sagst die Menge der entscheidbaren Mengen. Eine Menge ist dann entscheidbar, wenn ihre charakteristische Funktion berechenbar ist.
(Es gibt dazu noch eine Umformung, dass man sagt, dass eine Menge M dann entscheidbar ist, wenn eine TM A (Turing-Maschine) ex. mit L(A)=M und die auf jeder Eingabe anhält [kann man leicht konstruieren])

Dahingegen ist eine Menge aufzählbar wenn eine totale, (turing-)berechenbare Funktion f:A -> B ex. mit f[A] = M (also die BIldmenge ist gleich M) oder anders:
Eine Menge ist aufzählbar, wenn eine TM A ex mit L(A)=M (aufpassen: hier muss die TM nicht immer stets halten!).

Die Beziehung, dass Rec (ent. Mengen) eine Teilmenge von Re (aufz. Mengen) lässt sich leicht zeigen:
Sei M ent., dann ist die ch. Funktion berechenbar. Diese Funktion ist total und berechnbar, also ist M nach Def. auch aufzählbar.

Es ist noch die Frage, ob nun Rec eine ECHTE Teilmenge ist oder nicht. Es ist eine echte Teilmenge, was man z.B. mit der Menge H zeigen kann.

H ist die Codierung des Halteproblems. Genauer:

Das Halteproblem ist die Frage, ob eine beliebige TM bei einer beliebigen Eingabe nach endlicher Zeit anhält.
Die Menge H ist die Menge der Ja-Instanzen des Halteproblems, also

H= {<A><w> | A hält bei der Eingabe von w (nahc endl. Zeit) an}.

Um die Menge besser zu erklären: Es wird hier von der universellen TM gebrauch gemacht. Diese kann eine bel. andere TM simulieren, indem diese in geeigneter Weise codiert wird (ihre endl. Kontrolle bzw. die Übergangsfunktion). Daneben wird dann noch das Wort w geschreiben.

Es lässt sich nun zeigen, dass H nicht entscheidbar ist:
man kann also nicht sagen, ob eine bel. TM bei bel. Eingabe nach endl. Zeit anhält.

Im F3 Skript sind dafür 3 Beweise angegeben, wobei einer ungefähr so aussieht:
Anngenommen H ist entscheidbar, dann ist die ch. Funktion berechenbar mit einer TM A_H. Die Tm erhält also immer Eingaben vom Typ <A><w> und gibt eine 1 aus, wenn A auf w hält, sonst 0.
Jetzt wird diese Tm schritrweise umgebaut. Anstatt <A><w>, kann auch nur <A> geschrieben werden, was dann einmal kopiert wird. Wir erhalten die TM A_H', da also überprüft, ob eine TM A auf ihrer eigenen Codierung anhält oder nicht. Diese wird nun zu einer TM A_H'' umgebaut, die, anstatt eine 1 zu drucken, einfach in einen Zustand geht, der zu einer Endlosschleife führt.
Jetzt kommt der Trick: man nimmt die TM A_H'' und schreibt ihre eigene Codierung <A_H''> auf das Band. Die TM A_H'' hält genau dann an (und druckt eine 0), wenn die nicht auf ihrer eigenen Eingabe hält. Dies ist ein klarer Widerspruch (ohne '…ie…'!).

Damit ist also gezeigt, dass H nicht entscheidbar. H ist aber aufzählbar (eine passende TM lässt sich leicht konstruieren). Damit ist also klar, dass Rec eine echte Teilmenge von Re ist.

Ja, Woansinn. REC sind also tatsächlich die entscheidbaren Mengen. Ich hab's nun auch im Skript gefunden (Def. 5.14). Der Google war da nicht so gesprächig, besonders weil alle Authoren rekursiv, rekursiv aufzählbar, abzählbar usw. irgendwie ständig vertauschen, anders bezeichnen oder sonst einen Schabernack damit anstellen, um uns zu verwirren. Irgendwann glaubt man dann seinem eigenen Denkvermögen nicht mehr … :p

Das REC die entscheidbaren Mengen sind, macht irgendwie auch Sinn, weil die charakteristischen Funktionen dieser Mengen ja mü-rekursiv sind. Ein wenig verwirrend ist es trotzdem.

Danke für die ausführliche Antwort.