Sätze und Zusammenhänge

Aufzählbarkeit und Semi-Entscheidbarkeit

Entscheidbarkeit und Aufzählbarkeit

Satz: Eine Menge M, mit M\subseteq A^*, ist entscheidbar genau dann, wenn M und A^*\setminus M (Komplementmenge) aufzählbare Menge sind.

Wir wollen den Beweis des Teils "Wenn M und A^*\setminus M aufzählbare Mengen sind, dann ist M eine entscheidbare Menge." mit einem ausführbaren Beispiel illustrieren.

Wir wählen für f die Aufzählprozedur für die ungeraden Zahlen und für g die Aufzählprozedur für die geraden Zahlen. Damit erzeugen wir die betrachteten Mengen M und A^*\setminus M.

Von beiden Mengen schauen wir uns jeweils 30 Elemente an.

Wie man sieht, haben wir es mit Mengen von Zahlwörtern zu tun.

Die Prozedure für \chi_M wurde so konstruiert, wie im Beweis angegeben. Erproben Sie selbst einige Aufrufbeispiele mit selbstgewählten Wörtern aus A^*, also Wörtern natürlicher Zahlen.