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 einer Funktion f:\mathbb{N}\rightarrow{}M die surjektiv und brechenbar ist und die Menge 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

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 die Wörter 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 dauert die Berechnung unendlich.

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.

Zur Illustration verwenden 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.

Die Menge der natürlichen Zahlwörter kann wie folgt gebildet werden:

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 eine berechenbare Funktion ist.
Die folgende Racket-Funktion beweist, dass M entscheidbar ist.