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.

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:

Aufzählbarkeit von Primzahlen

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

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

$p(n) = \left\{\begin{array}{cc}n; wenn \ prime?(n)\\ 2; sonst\\ \end{array}\right. $

Algorithmus:

Aufbauprozedur für A*

Ausgehend von der leeren Menge wird an diese ein Element des Alphabets angefügt und es entstehen entsprechend viele neue Mengen. Diese Prozedur kann nun beliebig oft wiederholt werden.