BuK/IIm18/Vorlesung3

Wiki-Quelltext dieser Seite.

=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 <math> A^* = \{a,b\}</math> und <math>M \subset A^* =\{w | w \in A^* \text{ und } |w|=3 \}</math>

z.z.: M entscheidbar

Lösung:

<math>
\chi_{M}(w) = \begin{cases}
true, & \text{wenn } w \in M \\
false, & \text{sonst}
\end{cases}
</math>

<math> w \in M  \text{ wenn } w==aaa || w==aba || w==aab || w==baa || w==bab || w==abb || w==bba || w==bbb; </math>

Die Menge M ist somit entscheidbar.


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

geg.: Menge M aller Wörter aus <math> A^* = \{a,b\}</math> und <math>M \subset A^* =\{aw' | w' \in A^* \}</math>

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.


[[Bild:S3romuel_Aufbauschema_60.png]]

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

Aufzählfunktion:

<math>
\f_{F}(n) = \begin{cases}
n, & \text{wenn sqrt(n)}  \in N \\
2, & \text{sonst}
\end{cases}
</math>

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