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

M ist eine aufzählbar unendliche Menge und damit existiert eine Funktion f:\mathbb{N}\rightarrow{}M, die surjektiv und berechenbar ist und die Menge M aufzählt.
M ist semi-entscheidbar, wenn eine Funktion \chi'_M:A^{\ast}\rightarrow{}\mathbb{B} existiert, die berechenbar ist.
Die folgende Umsetzung in Racket beweist, dass M semi-entscheidbar ist, wenn die Aufzählfunktion f gegeben ist.

Beispiel

Gegeben sei das Alphabet ("a" "b" ... "z"). Die Menge M ist die Menge der Wörter, die sich aus der Verkettung mit dem Buchstaben "a" bilden lassen. Die folgende Funktion f zählt diese Menge auf.

Der Aufruf der Funktion \chi'_M berechnet, ob das gegebene Wort in M enthalten ist.

Wird ein Wort aus A^{\ast}\backslash{}M als Parameter übergeben, so stoppt die Berechnung nicht.

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 die surjektiven, berechenbaren Funktionen f_M: \mathbb{N} \mapsto M und f_{A^{\ast}\backslash{}M}: \mathbb{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.

Zur Illustration legen wir fest, dass A^{\ast} die Menge der natürlichen Zahlwörter, M die Menge der Zahlwörter für die geraden Zahlen und A^{\ast}\backslash{}M die Menge der Zahlwörter für die ungeraden Zahlen darstellen.

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

Die Mengen M und A^{\ast}\backslash{}M sind aufzählbar. D.h. es existiert eine Funktion f_M:\mathbb{N}\rightarrow{}M sowie eine Funktion f_{M\backslash{}A^{\ast}}:\mathbb{N}\rightarrow{}M\backslash{}A^{\ast}. M ist entscheidbar wenn \chi_M:A^{\ast}\rightarrow{}\mathbb{B} eine berechenbare Funktion ist.
Die folgende Racket-Funktion beweist, dass M entscheidbar ist. Die Funktion f-m ist die Aufzählfunktion der Menge M und die Funktion f-m2 ist die Aufzählfunktion der Komplementärmenge M\backslash{}A^{\ast}.

Beispiel

Wie oben in der Aufgabenstellung ist A^{\ast} die Menge aller Zahlwörter der natürlichen Zahlen. M ist die Menger der Zahlwörter der geraden Zahlen und wird aufgezählt durch:

Die Komplementärmenge M\backslash{}A^{\ast} ist demzufolge die Menge der Zahlwörter der ungeraden Zahlen und wird aufgezählt durch:

Die Funktion \chi_M berechnet für jedes Zahlwort einen Rückgabewert (Wahr oder Falsch).