Beweis

Aufgabenstellung

Zeigen Sie, dass \wp(A^*) für ein beliebiges Alphabet A eine überabzählbar unendliche Menge ist.

Lösung

Entscheidbarkeit endlicher Mengen

Aufgabenstellung

Implementieren Sie eine Scheme-Prozedur chi-endlich, die eine natürliche Zahl n und eine Liste L nimmt und entweder \#t oder \#f zurück gibt, 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

Aufzählbarkeit

Aufgabenstellung

Schreiben Sie eine Scheme-Prozedur, die die Menge der Quadratzahlen aufzählt.

Lösung

Semientscheidberkeit

Aufgabenstellung

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.

Lösung