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

Lösung

Semientscheidberkeit

Aufgabenstellung

Lösung