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:
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\}.
Aufgabe 11
Weisen Sie nach, dass die Menge M aller "Wörter" aus \{a,b\}^*, die mit a beginnen, semi-entscheidbar ist.
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.