Hi,

die definition von aufzählbar und abzählbar glaube ich soweit verstanden zu haben. auch dass eine aufzählbare menge automatisch eine abzählbare menge ist, leuchtet mir ein. ich versteh aber nicht, warum eine abzahlbare menge nicht gleichzeitig auch eine aufzählbare ist. abzählbar ist ja eine menge, wenn sie gleichmächtig zu N ist. aber wenn eine menge M gleichmächtig zu N ist, muss es ja eine surjektive abbildung von N nach M geben. also ist die menge M doch auch gleichzeitig aufzählbar, oder?
laut f3-skript gibt es aber abzählbare mengen, die nicht aufzählbar sind. weiss jemand, wo bei dieser sache mein denkfehler liegt?

(Edit: Topictitel)

bei google 'aufzählbar und abzählbar' eintippen bringt schon die ein oder andere Seite zu sowas,

siehe z.B.
http://nelli.uni-erlangen.de/Nelli/k3/v4_9_abzaehlbar_und_aufzaehlbar.xml

irgendwo wird sich sicher auch ein deutliches Beispiel finden

abzählbar ist ja eine menge, wenn sie gleichmächtig zu N ist.

Richtig.

aber wenn eine menge M gleichmächtig zu N ist, muss es ja eine surjektive abbildung von N nach M geben.

Ebenfalls richtig.

also ist die menge M doch auch gleichzeitig aufzählbar, oder?

Nein. Der entscheidende Unterschied ist, dass eine Menge
[img]http://mokrates.de/cgi-bin/texstring?A%5Csubseteq%5CSigma%5E*[/img] aufzählbar ist genau dann, wenn es eine
berechenbare totale surjektive Abbildung von N nach
A gibt, während eine Menge A abzählbar ist genau dann,
wenn es irgendeine totale surjektive Abbildung von N
nach A gibt.

Kurz: Für die Abzählbarkeit reicht eine beliebige
Abbildung, für die Aufzählbarkeit braucht man eine
berechenbare.

(Außerdem ist Aufzählbarkeit eine Eigenschaft von Sprachen
und Abzählbarkeit eine Eigenschaft von beliebigen Mengen.)

Die Abzählbarkeit macht also nur eine Aussage darüber,
"wieviele" Elemente in einer Menge enthalten sind,
während Aufzählbarkeit bedeutet, dass man mit einem
Algorithmus im Prinzip (damit meine ich: abgesehen davon,
dass es unendlich lange dauern kann) alle Elemente der
Menge nacheinander in irgendeiner Reihenfolge hinschreiben
kann.

Was man zur Abzählbarkeit wissen sollte, ist, dass diese
Eigenschaft für die in F behandelten Sprachen ziemlich
uninteressant ist, weil alle Sprachen - also Teilmengen
von [img]http://mokrates.de/cgi-bin/texstring?%5CSigma%5E*[/img] - abzählbar sind (denn [img]http://mokrates.de/cgi-bin/texstring?%5CSigma%5E*[/img] ist
selbst abzählbar, erst recht ihre Teilmengen).

Interessant wird die Abzählbarkeit als Eigenschaft von
Mengen von Sprachen. So ist zum Beispiel zu einem bestimmten
Alphabet die Menge der aufzählbaren Sprachen abzählbar,
aber die Menge aller Sprachen nicht (wird bestimmt im Skript
bewiesen, sonst erkläre ich das gerne).

Aufzählbarkeit ist dagegen eine "nichttriviale" Eigenschaft
von Sprachen: die oft bemühte [img]http://mokrates.de/cgi-bin/texstring?L_d%3D%5C%7Bw_i%5Cin%5CSigma%5E*%5Cmid%20w_i%5Cnotin%20L(A_i)%5C%7D[/img]
ist zum Beispiel nicht aufzählbar, genauso wie viele andere
Sprachen (tatsächlich sind sogar die meisten Sprachen nicht
aufzählbar!).

Ich hoffe, das trägt etwas zur Klärung der Begriffe bei [img]http://www.fb18.de/gfx/23.gif[/img]

Eine Menge M heißt ebenfalls rekursiv aufzählbar, falls sie leer ist.

Ich hoffe, das trägt etwas zur Klärung der Begriffe bei [img]http://www.fb18.de/gfx/23.gif[/img]

jo, danke georg, das hat es.

ich hätte da mal eine frage zur entscheidbarkeit.

nach der definition im skript ist eine menge entscheidbar, wenn es eine turingmaschine gibt, die die charakteristische funktion dieser menge berechnet. aufgrund des halteproblems weiss man aber nie, ob eine tm bei allen eingaben hält und somit auch nicht, ob sie immer genau das tut, das sie tun soll. steht das nicht im widerspruch zur entscheidbarkeit einer menge? denn man weiss doch wegen des halteproblems nie genau, ob eine tm für jede eingabe die charakteristische funktion berechnet. oder ist das doch kein widerspruch?

ich hätte da mal eine frage zur entscheidbarkeit.

nach der definition im skript ist eine menge entscheidbar, wenn es eine turingmaschine gibt, die die charakteristische funktion dieser menge berechnet. aufgrund des halteproblems weiss man aber nie, ob eine tm bei allen eingaben hält und somit auch nicht, ob sie immer genau das tut, das sie tun soll. steht das nicht im widerspruch zur entscheidbarkeit einer menge? denn man weiss doch wegen des halteproblems nie genau, ob eine tm für jede eingabe die charakteristische funktion berechnet. oder ist das doch kein widerspruch?

Bei der Berechnung der charakteristischen Funktion geht es nur darum, dass die Turingmaschine diese berechnet, sprich immer eine 1 oder 0 ausgibt für jede Eingabe Element der Menge. Danach muss sie nicht anhalten, das wird an keiner Stelle gefordert. :)

Bei der Berechnung der charakteristischen Funktion geht es nur darum, dass die Turingmaschine diese berechnet, sprich immer eine 1 oder 0 ausgibt für jede Eingabe Element der Menge. Danach muss sie nicht anhalten, das wird an keiner Stelle gefordert. :)

hm, aber in einem buch von mir wird bei der definition von entscheidbarkeit gefordert, dass es eine tm gibt, die auf alle eingaben hält.

*Skript durchblätter*
Also eine Menge ist entscheidbar, wenn die charakteristische Funktion berechenbar ist.

Turingberechenbar ist eine Funktion, wenn es eine DTM gibt, die vom Anfangszustand mit x als Eingabe in den Endzustand mit y als Ausgabe kommt, genau dann wenn f(x)=y.

Von daher stimmt meine Aussage nicht, die TM hält dann.

Das Halteproblem für Turing-Maschinen ist die Frage, ob eine beliebig vorgegebene Turing-Maschine bei einem frei ausgewählten Wort als Eingabe nach endlicher Zeit anhält.

Für die charakteristische Funktion nehmen wir allerdings keine beliebige TM und keine beliebige Eingabe.

Für die charakteristische Funktion nehmen wir allerdings keine beliebige TM und keine beliebige Eingabe.

ok was das halteproblem betrifft hast du mich überzeugt [img]http://www.fb18.de/gfx/25.gif[/img]

aber irgendwie verwirrt mich in diesem zusammenhang der satz von rice noch etwas. denn der besagt ja, dass man für keine tm entscheiden kann, ob sie eine bestimmte funktion berechnet. also kann man demnach auch nicht entscheiden, ob eine tm die charakteristische funktion von einer menge berechnet.
ist mit diesem unentscheidbar gemeint, dass es für eine bestimmte eingabe nicht entschieden werden kann oder kommt diese unentscheidbarkeit daher, dass man nicht für ALLE eingaben überprüfen kann, ob die tm diese funktion berechnet?

aber irgendwie verwirrt mich in diesem zusammenhang der satz von rice noch etwas. denn der besagt ja, dass man für keine tm entscheiden kann, ob sie eine bestimmte funktion berechnet.

Nein. Man kann keinen Algorithmus angeben, der fuer alle TM entscheidet, ob sie eine bestimmte Funktion berechnen. Fuer einzelne TM ist das aber kein Problem.

also ich fass mal zusammen:
es gibt keinen algorithmus (bzw. tm), der prüfen kann, ob irgendeine tm bei irgendeiner eingabe hält. genausowenig gibt es einen algorithmus, der prüfen kann, ob irgendeine tm eine bestimmte funktion berechnet.
für eine bestimmte tm kann man aber schon entscheiden, ob sie bei einer bestimmten eingabe terminiert bzw. eine bestimmte funktion berechnet…jetzt verstannden? [img]http://www.fb18.de/gfx/16.gif[/img]

Jo, so siehts aus.

[img]http://www.fb18.de/gfx/bounce.gif[/img] juhu