Nach unserem F3-Skript ist eine Menge M (die eine Teilmenge von \Sigma^* ist) aufzählbar gdw. sie leer ist (dies ist ein einfacher Sonderfall) oder aber folgendes gilt:
Es gibt eine totale Funktion g : N -> \Sigma^* (N sind die natürlichen Zahlen). Total heisst, dass für jede natürliche Zahl n g(n) auch wirklich definiert ist. Für g soll nun gelten, dass g(N) = M ist, dass also für jedes Element m aus M mindestens eine natürliche Zahl n exisitert mit g(n) = m. Zudem soll die Funktion g Turing-berechenbar sein! Das wiederrum heisst, dass eine DTM exisitert, die von der Startkonfiguration q_0 n (wobei q_0 der Startzustand ist und n eine natürliche Zahl, bzw. eigentlich eine Kodierung z.B. durch n+1 0en, man kann nämlich nicht jede natürliche Zahl in ein einzelnes Kästchen schreiben, da dann das Bandalphabet alle natürlichen Zahlen umfassen also unendlich gross sein müsste) aus in die Endkonfiguration q_e m übergeht, wobei q_e ein Endzustand ist und m eine Zeichenkette aus \Sigma^*. Sie (die DTM) tut dies gdw. g(n) = m gilt. — Verständlich? Sonst bitte weiterfragen [img]
http://www.fb18.de/gfx/25.gif[/img]
Soviel zur Definition von Auszählbarkeit im Skript. Es wird gleich nach Definition 2.16 in Theorem 2.17 aber gezeigt, dass dies äquivalent dazu ist, dass eine DTM exisitert mit L(A) = M. (So ist die Definition bspw. im Hopcroft/Ullman/Motwani und einigen anderen Büchern.) D.h. eine Menge M ist aufzählbar gdw. eine TM exisitert, die gerade diese Menge akzeptiert.
[Bemerkung: Es ist nicht nötig, dass die TM auf allen Eingaben hält! Tut sie dies (hält sie also insb. auch auf den Worten, die sie nicht akzeptiert) hat man sogar eine entscheidbare Menge. Dies ist aber so auch nicht im Skript definiert, aber äquivalent. (Man nehme die Definition aus dem Skript und halte nach der Ausgabe von 0 bzw. 1, bzw. nachdem man gehalten hat schreibe man noch 0 oder 1 auf das Band.)]
Der Witz ist dann, dass es auch Mengen gibt, die nicht mehr aufzählbar sind (z.B. die "Diagonalsprache" L_d im Skript). Was wegen der Turing'schen/Chur'schen These interesant ist. Diese Mengen sind dann nämlich auch von uns nicht berechenbar.
Hilft dir das schon?
Cheers,
Frank
P.S. Mit obigem kannst du dir schnell überlegen, dass jede endliche Menge aufzählbar sein muss. Du kannst eine TM bauen, die jedes Wort dieser Menge akzeptiert, indem du die Wörter einfach in die Zustände codierst. (Die endliche Menge ist sogar regulär, konstruier einfach einen NFA, der einen Start- und einen Endzustand hat, von dem Startzustand gehen dann Kanten zum Endzustand die jeweils mit einem der Wörter deiner Menge beschriftet sind.)