Sollte etwa die Menge abzählbar sein?

Genau. Es ist ja . ist abzählbar, und Teilmengen von abzählbaren Mengen sind ebenfalls abzählbar.

Abzählbar sind alle Mengen M, für die eine bijektive Funktion f: N -> M existiert, also eine Abbildung, die jedem Element aus N genau ein Element aus M zuordnet (somit kann man von jedem Element von M sagen, das "wievielte" es ist).

Aufzählbar ist eine Menge M, wenn eine Turingmaschine existiert, die jedes Element der Menge genau einmal auf ihr Ausgabeband schreibt.

edit: endliche Mengen M sind auch abzählbar, allerdings gibt es für diese natürlich keine Bijektion von N nach M

Da beisst sich doch irgendwas...?

So wird es auch im F3-Skript definiert. Wobei dann dort auch gezeigt wird, dass dies äquivalent dazu ist, dass eine TM exisitert, die diese Menge akzeptiert. (Damit ist dann klar, dass die Definition im Hopcroft/Ullman/Motwani zu der im Skript äquivalent ist. Im Schöning wird das aber zumindest auch erwähnt.)

Cheers,
Frank

P.S. Und *bitte* das ist nicht der "F2/F3-Schöning". In F2/F3 kann man doch noch so viel mehr Lernen, als in einem Büchlein mit dem Wörtchen "Kurzgefaßt" im Titel zu finden ist

P.P.S. Was nicht heisst, dass man mit dem Buch nicht seinen Spass haben könnte

Ja, genau so hab ichs mir auch gemerkt. Und auch einmal für mich selber begründet, warum die Definitionen äquivalent sind, aber um diese Uhrzeit komm ich nicht mehr drauf

Busy Beaver *duck*

Beispiele für nicht Turing-berechenbare Funktionen gibts in F3 glaub ich noch nicht. (Mal abgesehen von und Konsorten, also die Charakteristischen Funktionen der nicht-aufzählbaren Mengen.)

Ich soll dir von der VdF (der Vereinigung der Funktionen) ausrichten, dass ein Grossteil ihrer Mitglieder empört darüber ist, dass du den charakteristischen Funktionen den Status so eine richtige Funktion zu sein aberkennst

Ernsthaft: Das sind doch Funktionen und damit auch Beispiele für nicht Turing-berechenbare Funktionen! Insb. ist L_d ja auch abzählbar, daher exisitert eine Funktion mit g(N) = L_d und auch die ist nicht Turing-berechenbar (sonst wäre L_d ja nach Definition gerade aufzählbar).

Und wenn du ein Beispiel der Art f(x,y) = x*y oder so etwas suchst (also Verknüpfungen mit bekannten Operatoren), dann sind diese doch intuitiv berechenbar und damit auch von einer TM berechenbar.

Cheers,
Frank

Ich soll dir von der VdF (der Vereinigung der Funktionen) ausrichten, dass ein Grossteil ihrer Mitglieder empört darüber ist, dass du den charakteristischen Funktionen den Status so eine richtige Funktion zu sein aberkennst

Ernsthaft: Das sind doch Funktionen und damit auch Beispiele für nicht Turing-berechenbare Funktionen!

Pff. Darf ich Dich an Deinen beleidigten Blick in der letzten PS-Stunde erinnern, als ich _genau_ das Argument gebracht hab?

Ich vergass zu erwähnen: Die fehlenden Komplemente zu suchen ist dem geneigten Leser als Übungsaufgabe überlassen

Das war nicht beleidigt, das war nachdenklich

...Frank

Im F3 Skript steht (S. 42, vers. WiSe2003/04):
"Dass es überabzählbare, d.h. nicht abzählbare Mengen gibt, ist aus anderen Veranstaltungen (z.B. F1, F2 oder M1) bekannt."

Das kam natürlich in diesen Veranstaltungen nicht vor, damit es gleich wieder vergessen werden soll...
Im Übrigen, F3 kümmert sich mehr um das Berechenbare und die dennoch auftretenden Probleme.
Warum also Grundlagen aus F2 wiederholen?
Man kann- und sollte besser - auch nicht immer wieder ganz von vorn beginnen und z.B. an den Mathe-Untericht aus der Schule anknüpfen....
Vorlesungen bauen (bisher jedenfalls) aufeinander auf.

Drum also in F3 nicht schon wieder die Definition von Abzählbarkeit.

Zur Zeit korrigiere ich die immer noch enthaltenen Fehler im F3-Skript.
Wenn's dann fertig ist, kommen wohl die ganz neuen Veranstaltungen im Bachelor Studiengang, und alles wird wiederverwendet und eingearbeitet...

nun ja ;)

also wenn ich mich recht erinnere wird in PNL ausführlich wiederholt was Petrinetze, gefärbt oder nicht, usw. sind,
praktisch

wirklich meist nicht allzu notwendig,
aber bei aufzählbar und abzählbar bietet sich das sehr sehr an!
gerade auf den Unterschied sollte man hinweisen,
wenn es nicht zu allgemeinen Rätselraten wie in diesem Thread hier kommen soll
(natürlich kann man das auch aus den Definitionen herleiten,
aber schöner wärs schon ;) )

(einzelne Meinung)

da ist was dran ;),
aber ich hoffte auf etwas umgangssprachliches
oder Verweis auf irgendwelche Fraktale oder ähnlich mysteriöses,

vielleicht die Berechnung der Primzahlen bei RSA ;)
egal

Nach unserem F3-Skript ist eine Menge M (die eine Teilmenge von \Sigma^* ist) aufzählbar  [...]
--- Verständlich? Sonst bitte weiterfragen

Danke fuer diese ausfuehrliche Erklaerung .

Ein Frage habe ich noch: Der Zahlenkoeper Q (Menge der
rationalen Zahlen) laut M1-Skript ist abzählbar - gut einsehbar.
Ist Q auch aufzählbar? Ich wuerde sagen ja.

Ich freue mich schon, wenn ich diese F-Pruefung hinter mir habe ...

Und sowas ist im Hauptstudium... Genau der Beweis kommt in F2 dran.

Nun ja, letztendlich kannst Du ja nur Zahlen verarbeiten, die Du in irgendeiner (endlichen!) Form speichern kannst.

Hm, es wäre ja denkbar, z.B. die Wurzel aus 2 tatsächlich als ein Symbol für die Wurzel und die Zahl 2 zu speichern und dann damit zu rechnen.

Immer diese Praktiker...

Und? Heisst das wir als angehende Informatiker interessieren uns nur für Dinge, die man endlich speichern kann?

Das wäre aber recht schade...

Cheers,
Frank

Nö, aber man sollte sich z.B. im Klaren darüber sein, dass der Datentyp "real" nichts mit der menge der reellen Zahlen zu tun hat (sieht man ja schon daran, dass man den Dezimalbruch 0.1 nicht in einer Real-Variable speichern kann, obwohl 0.1 jetzt ja noch nicht mal ne tolle reelle Zahl ist sondern nur aus Q).

Also nicht berechenbare Funktionen kann man sich doch prima mit dem Satz von Rice und dann der Erweiterung von charakteristischen Funktionen konstruieren. Z.B. sind folgende Funktionen unberechenbar:

(d.h., f_k gibt an, wieviele W�rter der L�nge k von M akzeptiert werden)

Oder die Funktion


( soll die Nerode-�quivalenz bzgl. sein), die von einer gegebenen Turingmaschine angibt, wieviele Zust�nde der Minimalautomat f�r die akzeptierte Sprache hat, oder 0, wenn die Sprache nicht regul�r ist.

Oder die Funktion l, die angibt, ob die Sprache leer ist.
Und so weiter. Und das sind jetzt nur die, die mir so eingefallen sind. Man kann sich da also viele Funktionen konstruieren. Von all diesen Funktionen zeigt man, wie gesagt, die Unberechenbarkeit leicht mit dem Satz von Rice.

Naja, man kann die Funktion ja schlecht durch Angabe eines Algorithmus spezifizieren Also muss eine andere Art der Definition verwendet werden. Oder was meintest du mit "Vorgehensweise"?

Mir scheint es, also wolltest du eine unberechenbare Funktion durch ein Berechnungsverfahren definieren! Das geht aber nur dann, wenn du ein Verfahren angeben kannst, das nicht von einer TM durchgeführt werden kann. Das würde aber der Church'schen These widersprechen!

Das ist aber keine prinzipielle Beschränkung! Man kann doch prima beliebig viele rationale Zahlen mit zwei ints speichern!
(natürlich ist das auch wieder durch die Länge der ints beschränkt aber auch das ist keine prinzipielle Beschränkung).

Und bei den rationalen hört es ja nicht auf! Man kann ja durch symbolische Repräsentation noch viel mehr verarbeiten als Q!
(Macht doch schon ein gewöhnliches Computer-Algebra-System im Taschenrechner)

Die charakteristische Funktion Berechen bar heißt, dass wenn du eine Menge M hast, dann der TM ein Wort w gibst, diese dir eine 1 als Ergebnis geben muss, wenn w element M, eine 0 wenn w nicht element M.

Wobei das auf eine Obermenge bezogen ist, also wenn
, dann ist M entscheidbar gdw. für alle die charakteristische Funktion berechenbar ist, also 1 wenn , und 0 wenn