BuK/IIm20/Vorlesung 3 Freudenberg

Wiki-Quelltext dieser Seite.

<br\>

-	es gibt überabzählbar viele Probleme aber nur abzählbar viele Lösungen <br\>
-	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) <br\>
-	total berechenbare Funktion: liefert für jedes Argument einen Funktionswert <br\>
-	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) <br\>
-	Folie 9: bei einer endlichen Menge handelt es sich um eine feste Anzahl von Wörtern <br\>
-	Beispiel 2: A* ist eine abzählbar unendliche Menge, d.h. jede Teilmenge von A* ist entweder abzählbar unendlich oder unendlich <br\>
Folie 10: <br\> 
-	wie viele Abbildungen gibt es und wie viele davon sind berechenbar (d.h. ich kann eine Prozedur angeben) <br\> 
-	wie viel Teilmengen von A* gibt es -> Antwort liefert die Kardinalität/ Mächtigkeit der Potenzmenge (Anzahl der Elemente in der Menge -> Potenzmenge) <br\>
-	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 <br\>
Folie 11: <br\>
-	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 <br\>
-	Wdh. Definiton Abzählbarkeit: eine Menge ist abzählbar, wenn es eine bijektive Abbildung auf die natürlichen Zahlen gibt <br\>
-	Folie 18: das ist eine Prozedur, die für bestimmte Mengen nicht stoppt <br\>