BuK/IIm12/Studenten/siclsche/Thema3

Wiki-Quelltext dieser Seite.

== Aufgabe 1 ==
Wie viele berechenbare charakteristische Funktionen gibt es?

''Hinweis: Potenzmenge unendlicher Mengen''

== Aufgabe 2 == 
'''Beispiel 1:'''

M ist die Menge aller Wörter aus $A^*$, die die Länge 3 besitzen, d.h.:

$A^* = \{a, b\}^* \text{ und } M \subset A^* = \{w \mid w \in A^*\text{ und } |w| = 3\}$

'''Beispiel 2''' abzählbar unendliche Menge

$ M $ ist die Menge aller Wörter, die aus beliebeig vielen $ a $'s und $ b $'s bestehen und mit $ a $ beginnen: $ A^* = \{a,b\}^* $ und $ M \subset A^* = \{w = aw' | w' \in A^* \} $ .

Zeigen Sie, dass die beiden Mengen aus den Beispielen entscheidbar sind. Schreiben Sie je eine entsprechende Prozedur für die jeweilige charakteristische Funktion

== 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.

Lösung:

== 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.

Lösung:

== Aufgabe 6 ==
Zeigen Sie, dass jede endliche Menge M aufzählbar ist.

Lösung:

== 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_0$ bijektiv auf G abbildet.

Lösung:

2. Definieren Sie eine Ordnungsrelation $p_<$ in G.

Lösung:

3. Geben Sie eine Funktion k zur Berechnung der Platznummer k(x, y) des betrachteten Gitterpunktes (x, y) an.

Lösung:

4. Geben Sie eine Aufzählprozedur für G an und begründen Sie deren Berechenbarkeit.

Lösung:

== Aufgabe 8 ==
Das Halteproblem ist semi-entscheidbar. Beweisen Sie diese Aussage.

== Aufgabe 9 ==
Geben Sie fur 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.

Lösung:

== Aufgabe 12 ==
Definieren Sie die Menge der geraden Zahlen (Zahlwörter) und die der ungeraden Zahlen (Zahlwörter) und veranlassen Sie das ProgrammingWiki die 30 ersten Elemente der Vereinigungsmenge (in aufsteigender Sortierung) auszugeben.

Lösung: