Vorlesung3
Inhaltsverzeichnis |
Entscheidbarkeit und Aufzählbarkeit
Aufgabe 1
Zeigen Sie, dass die beiden Mengen aus den Beispielen entscheidbar sind. Schreiben Sie je eine entsprechende Prozedur für die jeweilige charakteristische Funktion (ProgrammingWiki).
Beispiel 1: endliche Menge
geg.: Menge M aller Wörter aus A^* = \{a,b\} und M \subset A^* =\{w | w \in A^* \text{ und } |w|=3 \}
z.z.: M entscheidbar
Lösung:
\chi_{M}(w) = \begin{cases} true, & \text{wenn } w \in M \\ false, & \text{sonst} \end{cases} w \in M \text{ wenn } w==aaa || w==aba || w==aab || w==baa || w==bab || w==abb || w==bba || w==bbb;Die Menge M ist somit entscheidbar.
Beispiel 2: abzählbar unendliche Menge
geg.: Menge M aller Wörter aus A^* = \{a,b\} und M \subset A^* =\{aw' | w' \in A^* \}
z.z.: M entscheidbar
Lösung:
\chi_{M}(w) = \begin{cases} true, & \text{wenn } w \text{ mit a beginnt und } w \in M \\ false, & \text{sonst} \end{cases}Die Menge M ist entscheidbar.
Aufgabe 2
Wie viele berechenbare charakteristische Funktionen gibt es?
Hinweis: Potenzmenge unendlicher Mengen
A^* ist eine abzählbar unendliche Menge, d.h. alle M \subseteq A^* sind abzählbar Mengen, entweder endlich oder unendlich.
Die Potenzmenge von A^* ist eine überabzählbar unendliche Menge, wodurch es überabzählbar unendlich viele Mengen M gibt.
\chi_{M} kann die Werte true \text{ oder } false annehmen.
Die überabzählbare Menge M bildet den Definitionsbereich der Funktionen \chi_{M}.
Das heißt es gibt überabzählbar viele charakteristische Funktionen \chi_{M}, für jede Teilmenge M von A^*.
Da es jedoch nur abzählbar unendlich viele Algorithmen gibt, verbleiben überabzählbar unendlich viele \chi-Funktionen, die nicht berechnet werden können. Nur abzählbar unendlich viele charakteristische Funktionen sind somit berechenbar.
Aufgabe 3
Zeigen Sie, dass die Menge der geraden Zahlen G eine aufzählbare Menge ist.
geg.: M_{G} die Menge der geraden Zahlen und M_{G} \in \mathbb{Z}
z.z.: M_{G} abzählbar, M_{G} berechenbar
Lösung:
Abzählbarkeit:
Die Menge der geraden Zahlen M_{G} ist eine Teilmenge der ganzen Zahlen \mathbb{Z}. Wie hier bewiewen wurde, sind die ganzen Zahlen abzählbar unendlich. Die Menge der geraden Zahlen M_{G} ist somit ebenfalls abzählbar unendlich.
Berechenbarkeit:
f(n)=\begin{cases}n & \text{, wenn }n\text{ gerade}\\2n & \text{, wenn }n\text{ ungerade}\end{cases}, mit n \in \mathbb{N}
Aufgabe 4
Zeigen Sie, dass die Menge der Primzahlen P aufzählbar ist.
Aufgabe 5
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.
Aufgabe 6
Zeigen Sie, dass jede endliche Menge M aufzählbar ist.
Aufgabe 7
Die Menge G der Gitterpunkte (0,0),(0,1),... einer x-y-Ebene ist aufzählbar.
1.Geben Sie eine Funktion f an, die \N bijektiv auf G abbildet.
f ist die Umkehrfunktion der Cantorschen Paarungsfunktion in Teilaufgabe 3.
f(n):\begin{cases} y = n-t \\ x =w-y \\ \end{cases}mit w(n)= \dfrac{sqrt(8*n+1)-1}{2}
und mit t= \dfrac{w(w-1)}{2}
2.Definieren Sie eine Ordnungsrelation p< in G
Mittels der in Teilaufgabe 1 gezeigten Funktion können nun jeder natürlichen Zahl ein Koordinatenpaar zugeordnet werden. Diese Zuordnung findet sich in der nachfolgenden Tabelle.
| Position || 0 || 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12 || 13 || 14 || 15 | ||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Gitterpunkt (x,y) | (0,0) | (0,1) | (1,0) | (0,2) | (1,1) | (2,0) | (0,3) | (1,2) | (2,1) | (3,0) | (0,4) | (1,3) | (2,2) | (3,1) | (4,0) | (0,5) |
Daraus kann man nun eine Ordnungsrelation festlegen mit aufsteigenden x- und y-Koordinaten:
(G, p_<) = {(0,0) < (0,1) < (1,0) < (0,2) < (1,1) < (2,0) < (0,3) < (1,2) < (2,1) < ...}
3. Geben Sie eine Funktion k zur Berechnung der Platznummer k(x,y) des betrachteten Gitterpunktes (x,y) an.
Eine Funktion k zur Berechnung der Platznummer ist die Cantorsche Paarungsfunktion, die folgendermaßen definiert ist:
k(x,y) = \frac{(x+y)+(x+y+1)}{2} + y.4. Geben Sie eine Aufzählprozedur für G an und begründen Sie deren Berechenbarkeit.
Aufgabe 8
Das Halteproblem ist semi-entscheidbar. Beweisen Sie diese Aussage.
Aufgabe 9
Geben Sie für die Menge FIBS der Fibonacci-Zahlwörter eine Aufzählfunktion an und begründen Sie deren Berechenbarkeit. Weisen Sie nach, dass FIBS eine semi-entscheidbare Menge ist. Zeigen Sie dass FIBS sogar entscheidbar ist.
Aufgabe 10
Übertragen Sie die vorhergehende Übungsaufgabe sinngemäß auf die Menge der Quadratzahlen QZ = \{n^2 | n\in\N\}.
Lösung:
Eine Aufzählfunktion kann folgendermaßen angegeben werden:
f(n) = \begin{cases} n, & \text{wenn sqrt(n)} \in \mathbb{N} \\ 2, & \text{sonst} \end{cases}Für die Entscheidbarkeit kann eine charakteristische Funktion angeben werden, die total berechenbar ist:
\chi_{QZ}(n) = \begin{cases} true, & \text{wenn } sqrt(n) \in \mathbb{N} \\ false, & \text{sonst} \end{cases}Aufgabe 11
Weisen Sie nach, dass die Menge M aller "Wörter" aus \{a,b\}^*, die mit a beginnen, semi-entscheidbar ist.
In Aufgabe 2 wurde die Entscheidbarkeit der Menge M nachgewiesen. Wenn eine Menge entscheidbar ist, ist diese folglich auch semientscheidbar.
Aufgabe 12
Definieren Sie die Menge der geraden Zahlen (Zahlwörter) und die der ungeraden Zahlen (Zahlwörter) und veranlassen Sie das ProgrammingWiki 30 Elemente der Vereinigungsmenge auszugeben.