Kapitel 3

Anzahl berechenbarer charakteristischer Funktionen

Die Wortmenge A* ist abzählbar unendlich. Für jedes Wort aus A* gibt es eine Funktion \chi, welche true oder false zurückgibt.

Von der Wortmenge A* wird nun die Potenzmenge P(A*) erzeugt, welche überabzählbar unendlich ist. Für jedes Element von P kann man nun ebenfalls eine eine Funktion \chi erzeugen. Diese Mengen P(P(A*)) haben ebenfalls überabzählbar unendlich viele Funktionen \chi. Dass einige davon nicht brechenbar sind, ist unerheblich.

Aufzählbarkeit gerader Zahlen

Zu zeigen ist, dass die Menge der geraden Zahlen G aufzählbar ist. Es gilt eine Aufzählprozedur g:\N \mapsto G zu finden. g muss berechenbar und surjektiv sein.

Wenn es eine solche Funktion gibt, dann ist G aufzählbar.

g(n)=2k wobei n,k\in \N

Algorithmus: