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