Aufzählbarkeit und Entscheidbarkeit

Aufgabe

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

Aufgabe

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

Lösung

Entscheidbarkeit bedeutet, es exisitert eine (totale) charakteristische Funktion \chi_{M_1,M_2}, welche ein Wort w aus M_2 als Eingabe erwartet und "1" zurückgibt, falls w \in M_1 und "0", falls w \in M_2\backslash{}M_1.

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 Racket. Verwenden Sie die entwickelten Racket-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