Vorlesung 3 Freudenberg

- es gibt überabzählbar viele Probleme aber nur abzählbar viele Lösungen
- Relativ entscheidbare Mengen: M1 ist relativ zu M2, wenn eine Funktion angegeben werden kann, die für alle Elemente aus M2 wahr oder falsch zurückgibt (M1, M2 und A* sind Wortmengen)
- total berechenbare Funktion: liefert für jedes Argument einen Funktionswert
- eine Menge ist gegenüber einer anderen Menge eigentlich immer relativ entscheidbar; wenn die andere Menge aber die Grundmenge ist, in der alle Wörter von A* enthalten sind, dann spricht man von absolut entscheidbar (man legt die Größte Menge aller Wörter zu Grunde)
- Folie 9: bei einer endlichen Menge handelt es sich um eine feste Anzahl von Wörtern
- Beispiel 2: A* ist eine abzählbar unendliche Menge, d.h. jede Teilmenge von A* ist entweder abzählbar unendlich oder unendlich
Folie 10:
- wie viele Abbildungen gibt es und wie viele davon sind berechenbar (d.h. ich kann eine Prozedur angeben)
- wie viel Teilmengen von A* gibt es -> Antwort liefert die Kardinalität/ Mächtigkeit der Potenzmenge (Anzahl der Elemente in der Menge -> Potenzmenge)
- es gibt überabzählbar unendlich viele charakteristische Funktionen, aber nur abzählbar unendlich viele Programme, also gibt es überabzählbar unendlich viele Funktionen, die nicht berechenbar sind
Folie 11:
- ich kann die Elemente der Teilmenge M nicht einfach durch aufzählen angeben, da ich gar nicht alle Elemente kenn, daher brauche ich eine Funktion f die mir die Elemente generiert
- Wdh. Definiton Abzählbarkeit: eine Menge ist abzählbar, wenn es eine bijektive Abbildung auf die natürlichen Zahlen gibt
- Folie 18: das ist eine Prozedur, die für bestimmte Mengen nicht stoppt