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}Aufgabe 2
Wie viele berechenbare charakteristische Funktionen gibt es?
Hinweis: Potenzmenge unendlicher Mengen
Aufgabe 3
Zeigen Sie, dass die Menge der geraden Zahlen G eine aufzählbare Menge ist.
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.
- Geben Sie eine Funktion f an, die \N bijektiv auf G abbildet.
- Definieren Sie eine Ordnungsrelation p< in G
- Geben Sie eine Funktion k zur Berechnung der Platznummer k(x,y) des betrachteten Gitterpunktes (x,y) an.
- 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.