Aufzählbarkeit und Entscheidbarkeit

Aufgabe

Drücken Sie den Beweis des folgenden Satzes mit Scheme aus. Wenn M eine aufzählbar unendliche Menge ist, dann ist M semi-entscheidbar.

Lösung

Entscheidbarkeit und Aufzählbarkeit

Aufgabe

Beweisen Sie: Wenn M entscheidbar ist, dann sind M und A^{\ast}\backslash{}M aufzählbar. Illustrieren Sie anschließend mit Scheme.

Lösung

Semi-Entscheidbarkeit

Aufgabe

Zeigen Sie auf der Basis der Semi-Entscheidbarkeit, dass wenn M und A^{\ast}\backslash{}M aufzählbar sind, M entscheidbar ist. Repräsentieren Sie den Beweis anschließend mit Scheme. Verwenden Sie die entwickelten Scheme-Prozeduren für folgendes Beispiel: A^{\ast} ist die Menge der natürlichen Zahlwörter, M die Menge der Zahlwörter für die geraden Zahlen und A^{\ast}\backslash{}M die Zahlwörter für die ungeraden Zahlen.

Lösung