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.

Das heißt wir können davon ausgehen, dass die Funktion \chi_{M,A^{\ast}}(w) exisitert.

Die Mengen M und A^{\ast}\backslash{}M sind aufzählbar, wenn es die surjektiven, berechenbaren Funktionen f_M: N \mapsto M und f_{A^{\ast}\backslash{}M}: N \mapsto A^{\ast}\backslash{}M existieren.

Diese Aufzählfunktionen können unter Verwendung von \chi_{M,A^{\ast}}(w) definiert werden. Dafür benötigen wir noch eine Funktion g, welche die Menge A^{\ast} aufzählt.

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