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


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


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