Vorlesung 3 Freudenberg

Aus ProgrammingWiki

- 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

ÜA: Zeigen Sie, dass die Menge der geraden Zahlen G eine aufzählbare Menge ist.

- aufzählbar = abzählbar + berechenbar
- 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.
- berechenbar: (define even_Zahlen (make-stream 2 (lambda (n) (n+2))))

ÜA: Zeigen Sie, dass die Menge der Primzahlen aufzählbar ist.

- abzählbar: Beweis durch Wiederspruch mit dem Fundamentalsatz der Arithmetik
- berechenbar: siehe Prozedur auf Folie 14

ÜA: Zeigen Sie, dass jede endliche Menge aufzählbar ist.

- 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
- berechenbar: wenn ich eine endliche Menge habe, dann kann ich alle Elemente dieser Menge angeben

ÜA: Das Halteproblem ist semi-entscheidbar. Beweisen Sie diese Aussage.

- 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
- das Halteproblem ist somit algorithmisch nicht entscheidbar

- Gibt es ein Programm, dass das Halteproblem löst?
- Eingabe: ein Programm P und eine Eingabe E
- Ausgabe (partielle Funktion X’M ): „Hält“ wenn P bei Eingabe E anhält „Hält nicht“ sonst.
- Annahme: es gibt ein Programm STOP, dass das Halteproblem löst und ein Programm POSTS (die Eingabe besteht aus einem Programm P)

POSTS: (1) STOP wird auf Programm P und Eingabe P eingesetzt
(2) Bei Ausgabe „Hält nicht“ hält das Programm POSTS an.
(3) Bei Ausgabe „Hält“ läuft das Programm POSTS in eine Endlosschleife und hält nie.

- Dann gilt: POTS angesetzt auf P hält an
⇐⇒ STOP angesetzt auf Programm P und Eingabe P gibt „Hält nicht“ aus
⇐⇒ P angesetzt auf P hält nicht an
- Setzen wir jetzt POTS auf sich selbst an: POTS angesetzt auf POTS hält an ⇐⇒ POTS angesetzt auf POTS hält nicht an
- -> hier stimmt was nicht; die Annahme, dass es ein Programm STOP gibt, welches das Halteproblem löst ist falsch