BuK/IIm20/Vorlesung 3 Freudenberg

Wiki-Quelltext dieser Seite.

-	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\>


'''ÜA: Zeigen Sie, dass die Menge der geraden Zahlen G eine aufzählbare Menge ist.''' <br\>
<br\>
-	aufzählbar = abzählbar + berechenbar <br\>
-	abzählbar: ich kann das 1. Element der geraden Zahlen -2- auf die natürliche Zahl 0 abbilden, das 2. Element -4- auf die natürliche Zahl 1, das 3. Element -6- auf die natürliche Zahl 2, usw. <br\>
-	berechenbar: (define even_Zahlen (make-stream 2 (lambda (n) (n+2)))) <br\>
<br\>
'''ÜA: Zeigen Sie, dass die Menge der Primzahlen aufzählbar ist.''' <br\>
<br\>
-	abzählbar: Beweis durch Wiederspruch mit dem Fundamentalsatz der Arithmetik <br\>
-	berechenbar: siehe Prozedur auf Folie 14 <br\>
<br\>
'''ÜA: Zeigen Sie, dass jede endliche Menge aufzählbar ist.''' <br\>
<br\>
-	abzählbar: die natürlichen Zahlen sind selbst eine endliche Menge; da jede Teilmenge einer endlichen Menge ebenfalls endlich ist, kann diese bijektiv auf die natürlichen Zahlen abgebildet sein <br\>
-	berechenbar: wenn ich eine endliche Menge habe, dann kann ich alle Elemente dieser Menge angeben <br\> 
<br\>
'''ÜA: Das Halteproblem ist semi-entscheidbar. Beweisen Sie diese Aussage.''' <br\>
<br\>
-	Halteproblem: für eine Berechnung mehrere Rechenschritte nach festen Regeln durchgeführt werden, entsteht eine Berechnungsvorschrift, ein sogenannter Algorithmus; Halteproblem beschreibt die Frage, ob die Ausführung eines Algorithmus zu einem Ende gelangt; Alan Turing bewies, dass es keinen Algorithmus gibt, der diese Frage für alle möglichen Algorithmen und beliebige Eingaben beantwortet <br\>
-	das Halteproblem ist somit algorithmisch nicht entscheidbar <br\>
<br\>
-	Gibt es ein Programm, dass das Halteproblem löst? <br\>
-	Eingabe: ein Programm P und eine Eingabe E <br\>
-	Ausgabe (partielle Funktion X’M ): 	„Hält“  		wenn P bei Eingabe E anhält
„Hält nicht“ 	sonst. <br\>
-	Annahme: es gibt ein Programm STOP, dass das Halteproblem löst und ein Programm POSTS (die Eingabe besteht aus einem Programm P) <br\>

'''POSTS:'''	(1) STOP wird auf Programm P und Eingabe P eingesetzt <br\>
		(2) Bei Ausgabe „Hält nicht“ hält das Programm POSTS an. <br\>
		(3) Bei Ausgabe „Hält“ läuft das Programm POSTS in eine Endlosschleife und hält nie. <br\>
<br\>
-	Dann gilt: POTS angesetzt auf P hält an <br\> 
⇐⇒ STOP angesetzt auf Programm P und Eingabe P gibt „Hält nicht“ aus <br\> 
⇐⇒ P angesetzt auf P hält nicht an <br\>
-	Setzen wir jetzt POTS auf sich selbst an: '''''POTS angesetzt auf POTS hält an ⇐⇒ POTS angesetzt auf POTS hält nicht an''''' <br\> 
-	-> hier stimmt was nicht; die Annahme, dass es ein Programm STOP gibt, welches das Halteproblem löst ist falsch <br\>