sirabien
Inhaltsverzeichnis |
Woche 2
Aufgabe 4
Beweisen Sie den folgenden Satz: Wenn M_{1}, M_{2}, M_{3} ... abzählbare Mengen sind, dann ist auch die Menge \bigcup_{n=1}^\infty {M_{n}} abzählbar.
m_{1}(i), m_{2}(i), m_{3}(i) …; i ∈ ℕ seien Indexfunktionen für M_{1}, M_{2}, M_{3} …
n(i); i ∈ ℕ sei Indexfunktion für \bigcup_{n=1}^\infty {M_{n}} (gesucht)
Cantorsches Diagonalisierungsverfahren 1. Art:
| |m_{1}(0) = n(0) | m_{1}(1) = n(1) | m_{1}(2) = n(5) | m_{1}(3) = n(6) | … |
| |m_{2}(0) = n(2) | m_{2}(1) = n(4) | m_{2}(2) = n(7) | m_{2}(3) = n(13) | … |
| |m_{3}(0) = n(3) | m_{3}(1) = n(8) | m_{3}(2) = n(12) | m_{3}(3) = n(17) | … |
| |m_{4}(0) = n(9) | m_{4}(1) = n(11) | m_{4}(2) = n(18) | m_{4}(3) = n(24) | … |
| |… | … | … | … | … |
Alternativ:
| |m_{0}(0) = n(0) | m_{0}(1) = n(2) | m_{0}(2) = n(5) | m_{0}(3) = n(9) | … |
| |m_{1}(0) = n(1) | m_{1}(1) = n(4) | m_{1}(2) = n(8) | m_{1}(3) = n(13) | … |
| |m_{2}(0) = n(3) | m_{2}(1) = n(7) | m_{2}(2) = n(12) | m_{2}(3) = n(18) | … |
| |m_{3}(0) = n(6) | m_{3}(1) = n(11) | m_{3}(2) = n(17) | m_{3}(3) = n(24) | … |
| |… | … | … | … | … |
Woche 3
Aufgabe 3
ÜA: Zeigen Sie, dass die Menge der geraden Zahlen G eine aufzählbare Menge ist.
Gesucht: f: ℕ ↦ G; berechenbar, surjektiv
$f(x) = \left\{\begin{array}{cc} x; wenn\ 2|x\\ (-1) \cdot x + 1; sonst\\ \end{array}\right. $
ÜA: Zeigen Sie, dass die Menge der Primzahlen P aufzählbar ist
Gesucht: f: ℕ ↦ P; berechenbar, surjektiv
$f(x) = \left\{\begin{array}{cc} x; wenn\ prime?(x)\\ 2; sonst\\ \end{array}\right. $
Existiert ein Algorithmus für f? wenn/sonst durch if/else implementierbar prime? Funktion existiert (siehe Folien)
↦ f ist berechenbar
ÜA: Wir wissen, dass A* eine abzählbar unendliche Menge ist. Zeigen Sie, dass A* auch aufzählbar ist. Hinweis: Hierzu ist es notwendig ein Aufbauschema für A* zu entwerfen und anschließend eine Prozedur dafür zu implementieren.
Für endliches Alphabet:
Bsp:
(als SVG)
Kreativaufgabe Schnittmenge zweier aufzählbarer Mengen
Woche 4
Teilaufgabe 2 - Indirekter Beweis (Max Wielsch, Raik Bieniek)
zu zeigen: Nicht jede Teilmenge M_2 einer aufzählbaren Menge M_1 ist aufzählbar.
oder: Wenn M1 eine aufzählbare Menge ist, dann gilt nicht für alle Teilmengen M_2 ⊆ M_1, dass sie aufzählbar sind.
Indirekter Beweis: Behauptung: Wenn M_1 aufzählbar, dann jede Teilmenge M_2 ⊆ M_1 ist aufzählbar.
Gegeben:
- f: ℕ ↦ M_1; aufzählbar (surjektiv; berechenbar)
- M_2 ⊆ M_1
- Satz 1: Wenn M_2 entscheidbar ⇔ M_2 und M_1 \setminus M_2 aufzählbar.
- Satz 2: Wenn M_2 aufzählbar → dann ist M_2 semientscheidbar.
Gesucht:
- g: ℕ ↦ M_2; aufzählbar (surjektiv; berechenbar), d. h. es gilt Satz 1.
$g(x) = \left\{\begin{array}{cc} f(x); wenn\ f(x) ∈ M_2\\v a; wenn f(x) ∈ M1\setminus M_2\\ \end{array}\right. $
laut Satz 2:
$Χ'_{M_2,M_1}(w) = \left\{\begin{array}{cc} wahr; (f(i) = w) ∈ M_2; für\ i\ von\ 0\ bis\ ∞\\ ⊥; sonst\\ \end{array}\right. $
$Χ_{M_2,M_1}(w) = \left\{\begin{array}{cc} wahr; (f(i) = w) ∈ M_2; für\ i\ von\ 0\ bis\ ∞\\ falsch; (f(i) = w) ∈ M_1\setminus M_2 \\ \end{array}\right. $
Χ'_{M_2,M_1} vs. Χ_{M_2,M_1}; entscheidbar ☇ semi-entscheidbar. → Behauptung falsch → Satz wahr.
Woche 5
Eine Menge M ⊆ Σ* heißt Turing-entscheidbar, wenn es eine Turing-Maschine P gibt, so dass
- für ∀w ∈ M gilt: q0 w ⊢^* qe x, qe ∈ E, x ∈ Γ.
- für ∀w ∉ M gilt: ¬(q0 w ⊢^* qe x).
Eine Menge M ⊆ Σ heißt Turing-aufzählbar, wenn es eine Turing-Maschine P gibt, so dass für ∀w ∈ Σ* gilt q0 w ⊢^* qe x, qe ∈ E, x ∈ M.
- Idee: Σ* ist aufzählbar und wird anstelle der natürlichen Zahlen verwendet.
Woche 7
Gödelisierung
Die Gödelisierung bezeichnet das Verfahren, ein Wort aus einer Wortmenge (A^*) auf die Menge der Zahlen abzubilden. Dadurch sind Probleme der "Wort-Welt", also Probleme, die mit Programmiersprachen beschrieben werden können, ebenso in der Zahlenwelt (Mathematik) darstellbar und lösbar.
Hilfsprozeduren
Zunächst werden für die Realisierung der Gödelfunktion einige Hilfsprozeduren benötigt, die die Teiloperationen der Primzahlenverschlüsselung kapseln.
Hauptprozedur
Die Hauptprozedur für die Gödel-Funktion ist nun mit den Hilfsfunktionen realisiert.
Umkehrung der Gödelisierung
Für die "Ent-Gödelisierung" muss nun aus einer Gödelnummer ein Wort aus der Wortmenge (Das Urbild der Abbildung) erzeugt werden, das mit der Gödel-Funktion benutzt wieder genau dieselbe Gödelnummer ergibt.