blatt #6

[Thomas]

ich hab die 2. Version genommen, da er dort sowas benutzt hat wie t(<F>) = <G>. Hab mir das erste nochma angeschaut und stimm dir zu, dass das wohl besser passt, wenn man P<M1> = <M2> setzt

[colajunkie]

zur 2:

PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken

Ich hab mir folgendes überlegt:
rekursiv aufzählbar ist ja bekanntlich äquivalent zu positiv semi-entscheidbar.
Was müsste eine TM denn leisten um diese semi-entscheidung treffen zu können?
Sie müsste für eine eingegebene TM C prüfen können ob diese in der Teilmenge liegt.
Dazu muss sie
a) prüfen können, dass in der Teilmenge keine TM D existiert mit <D> << <C>, denn nur dann ist C minimal
b) prüfen können ob C die weiteren kriterien für die Teilmenge erfüllt.
Unter der Annahme (obda) dass b) kein Problem darstellt gilt allerdings: die TM muss ALLE Elemente der Teilmenge durchgehen um absolut sicher zu sein dass es keine minimalere TM gibt als C. Da die Teilmenge aber unendlich ist, ist das nicht möglich (bei endlichen wäre das kein Problem, würde halt eventuell dauern^^), die Problematik entspricht damit eigentlich dem Halteproblem.
Es kann demnach aber keine TM geben die die Teilmenge positiv Semi-entscheidet (da genau dann, wenn C minimal ist, die TM nicht halten würde).

keine ahnung ob das so richtig ist, ich werds mal so abgeben^^