Drücken Sie den Beweis des folgenden Satzes mit Racket aus.
Wenn eine aufzählbar unendliche Menge ist, dann ist semi-entscheidbar.
Lösung
ist eine aufzählbar unendliche Menge und damit existiert eine Funktion , die surjektiv und berechenbar ist und die Menge aufzählt. ist semi-entscheidbar, wenn eine Funktion existiert, die berechenbar ist.
Die folgende Umsetzung in Racket beweist, dass semi-entscheidbar ist, wenn die Aufzählfunktion gegeben ist.
Beispiel
Gegeben sei das Alphabet ("a" "b" ... "z").
Die Menge ist die Menge der Wörter, die sich aus der Verkettung mit dem Buchstaben "a" bilden lassen. Die folgende Funktion zählt diese Menge auf.
Der Aufruf der Funktion berechnet, ob das gegebene Wort in enthalten ist.
Wird ein Wort aus als Parameter übergeben, so stoppt die Berechnung nicht.
Entscheidbarkeit und Aufzählbarkeit
Aufgabe
Beweisen Sie: Wenn entscheidbar ist, dann sind und aufzählbar. Illustrieren Sie anschließend mit Racket.
Lösung
Entscheidbarkeit bedeutet, es exisitert eine (totale) charakteristische Funktion , welche ein Wort aus als Eingabe erwartet und "1" zurückgibt, falls und "0", falls .
Das heißt wir können davon ausgehen, dass die Funktion exisitert.
Die Mengen und sind aufzählbar, wenn die surjektiven, berechenbaren Funktionen
und existieren.
Diese Aufzählfunktionen können unter Verwendung von definiert werden. Dafür benötigen wir noch eine Funktion , welche die Menge aufzählt.
Zur Illustration legen wir fest, dass die Menge der natürlichen Zahlwörter, die Menge der Zahlwörter für die geraden Zahlen und die Menge der Zahlwörter für die ungeraden Zahlen darstellen.
Semi-Entscheidbarkeit
Aufgabe
Zeigen Sie auf der Basis der Semi-Entscheidbarkeit, dass wenn und aufzählbar sind, entscheidbar ist. Repräsentieren Sie den Beweis anschließend mit Racket.
Verwenden Sie die entwickelten Racket-Prozeduren für folgendes Beispiel: ist die Menge der natürlichen Zahlwörter, die Menge der Zahlwörter für die geraden Zahlen und die Zahlwörter für die ungeraden Zahlen.
Lösung
Die Mengen und sind aufzählbar. D.h. es existiert eine Funktion sowie eine Funktion . ist entscheidbar wenn eine berechenbare Funktion ist.
Die folgende Racket-Funktion beweist, dass entscheidbar ist. Die Funktion f-m ist die Aufzählfunktion der Menge und die Funktion f-m2 ist die Aufzählfunktion der Komplementärmenge .
Beispiel
Wie oben in der Aufgabenstellung ist die Menge aller Zahlwörter der natürlichen Zahlen. ist die Menger der Zahlwörter der geraden Zahlen und wird aufgezählt durch:
Die Komplementärmenge ist demzufolge die Menge der Zahlwörter der ungeraden Zahlen und wird aufgezählt durch:
Die Funktion berechnet für jedes Zahlwort einen Rückgabewert (Wahr oder Falsch).
