BuK-Übung03 G2
Inhaltsverzeichnis |
Aufzählbarkeit und Entscheidbarkeit
Aufgabe
Zeigen Sie, dass \varphi(A^*) für ein beliebiges Alphabet A eine überabzählbar unendliche Menge ist.
Lösung
TODO
Aufgabe
Implementieren Sie eine Scheme-Prozedur chi-endlich, die eine natürliche Zahl n und eine Liste L nimmt und entweder #t oder #f zurückgibt, je nachdem ob n \in L oder n \notin L gilt. Stellen Sie für den Entwurf von chi-endlich die erforderlichen Hilfsprozeduren bereit.
Lösung
Aufgabe
Schreiben Sie eine Scheme-Prozedur, die die Menge der Quadratzahlen aufzählt.
Lösung
Man sagt f zählt M auf, wenn gilt:
M \subseteq A^*
f ist eine totale Funktion der Form f: N \mapsto M
f ist surjektiv und berechnbar und deren Wertebereich ist M = {f(0), f(1), \dots}
Dabei ist M die Menge der Quadratzahlen. Die Funktion f muss also eine surjektive Abbildung der natürlichen Zahlen N auf die Menge M vornehmen und berechenbar sein. Dazu benötigen wir die sogenannte Aufzählfunktion g für die Menge der Quadratzahlen.
f(n) = \begin{cases}g(n), & \text{wenn } g(n) \in M \\4, & \text{sonst}\end{cases}Die Menge M erzeugen wir mit Hilfe von Streams.
Damit können wir f wie folgt implementieren:
Aufgabe
Schreiben Sie eine Scheme-Prozedur, die die Menge der Quadratzahlen relativ zur Menge der natürlichen Zahlen semi-entscheidet.
Hinweis: Implementieren Sie eine Prozedur für die (allgemeingültige) \chi^'_M und wenden Sie sie auf die Menge (stream) der natürlichen Zahlen an. Überlegen Sie sich vor dem Aufruf genau, welche Ausgabe Sie erwarten.