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:

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}