s3roried
Aus ProgrammingWiki
Inhaltsverzeichnis |
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.
