Woher weiss man, dass Re != Rec ist?
Hab dazu im Skript leider nix gefunden. Es wird zwar gesagt,
dass Re < Rec (< entspricht hier echte Teilmenge), aber bewiesen wird das nirgendwo. Bei den Gprots habe ich allerdings so ne Frage gefunden . Würd mich also freuen wenn mir jemand n Beweis geben oder verlinken könnte.

Wurde hier bereits besprochen.

Na ja, eine Begründung wurde dort aber leider auch nicht geliefert.

Aber ich habe mittlerweile selbst noch etwas nachgedacht:
Eine Menge ist ja aufzählbar, wenn es eine TM gibt, die diese Menge
als Sprache akzeptiert. Eine Menge ist entscheidbar wenn es TM gibt,
die diese Menge als Sprache akzeptiert, und die TM auf jeder Eingabe
w e E* anhält.
Daraus folgt schonmal, dass jede entscheidbare Menge auch aufzählbar ist.
Da es jedoch auch TMs gibt die eine Sprache akzeptieren, jedoch
nicht auf jeder Eingabe w e E* anhalten, sind nicht alle aufzählbaren Mengen entscheidbar.
Damit wäre gezeigt, dass Rec < Re.

Reicht das als Begründung, oder muss man noch zeigen, dass es wirklich TMs gibt die eine Sprache akzeptieren, jedoch nicht auf jeder Eingabe w e E* halten?

Naja, dort wurde ja kein Beweis für diese Tatsache
angegeben. Einen solchen kann ich im Moment auch
nicht im Skript entdecken. Deshalb geb ich hier mal
einen an.

Im Skript wird zumindest erwähnt, dass das Halteproblem
aufzählbar ist (dass es nicht entscheidbar ist, wird
sogar bewiesen). Dass das der Fall ist, sieht man an
Satz 2.19 (zumindest im WiSe04/05-Skript heißt er so).
Der sagt: eine Sprache ist aufzählbar genau dann, wenn
es ein DTM gibt, die sie akzeptiert.

Eine DTM, die das Halteproblem akzeptiert, konstruiert
man aber leicht: Man nimmt sich die UTM und ändert
sie so ab, dass sie akzeptiert, sobald die simulierte
TM hält. Solange die simulierte TM rechnet, rechnet die
UTM eben auch weiter ohne zu akzeptieren.

Klar?


Edit: Ups, da warst du schneller… Hmm, nein, das
reicht als Erklärung nicht aus, denn du musst ja
beweisen, dass es Sprachen gibt, für die es keine
TM gibt, die immer hält. (Es gibt sogar für reguläre
Sprachen TMs, die nicht immer halten, aber das beweist
eben nicht, dass diese Sprachen dann nicht entscheidbar
sind (die sind schließlich auch entscheidbar[img]http://www.fb18.de/gfx/28.gif[/img])).

ok, danke