BuK/IIm10/BuK-Übung04 G1

Wiki-Quelltext dieser Seite.

=Aufzählbarkeit und Entscheidbarkeit=
==Aufgabenstellung==
Drücken Sie den Beweis des folgenden Satzes mit Racket aus.
Wenn ''M'' eine aufzählbar unendliche Menge ist, dann ist ''M'' semi-entscheidbar.
==Lösung==

=Entscheidbarkeit und Aufzählbarkeit=
==Aufgabenstellung==
Beweisen Sie: Wenn ''M'' entscheidbar ist, dann sind ''M'' und ''A''* \ ''M'' aufzählbar. Illustrieren Sie anschließend mit Racket.
==Lösung==

=Semi-Entscheidbarkeit=
==Aufgabenstellung==
Zeigen Sie auf der Basis der Semi-Entscheidbarkeit, dass wenn ''M'' und ''A''* \ ''M'' aufzählbar sind, ''M'' entscheidbar ist. Repräsentieren Sie den Beweis anschließend mit Racket. Verwenden Sie die entwickelten Racket-Prozeduren für folgendes Beispiel: ''A''* ist die Menge der natürlichen Zahlwörter, ''M'' die Menge der Zahlwörter für die geraden Zahlen und ''A''* \ ''M'' die Zahlwörter für die ungeraden Zahlen.
==Lösung==