Uebung3
Aus ProgrammingWiki
Vereinigung mit Streams
Inhaltsverzeichnis |
Übung 3
Entscheidbarkeit einfacher Mengen
Zu zeigen ist die Entscheidbarkeit der beiden Mengen $M1$ und $M2$. Dazu reicht es eine entsprechende Charaktersitische Funktion $\chi_{M_x}(w)$ zu finden.
Bsp1
$A^*={a,b}^*$ und $M_1 \subset A^* = \{w | w \in A^* \text{ und } |w| = 3\}$ $M_1$ ist die Menge aller Wörter aus $A^*$, die die Länge 3 beseitzen, d.h. $M_1 = \{aaa, aba, aab, baa, bab, abb, bba, bbb\}$
Da die Menge endlich ist, können einfach alle Elemente überprüft werden. Somit ergibt sich $\chi_{M_1}(w)$.
$$ \chi_{M_1}(w) = \begin{cases} wahr, & \text{wenn } w==aaa || w==aba || w==aab || w==baa || w==bab || w==abb || w==bba || w==bbb;\\ falsch, & \text{sonst} \end{cases} $$
Bsp 2
Abzählbar unendliche Menge. $M_2$ ist die Menge aller Wörter, die aus beliebig vielen a's und b's bestehen und mit a beginnen. $A^* = {a, b}^*$ und $M1 \subset A^* = {w = aw' | w' \in A^*}$
Da es reicht das erste Element zu überprüfen, ist die Menge entscheidbar. Dazu sei $w \in M_1 = w_1 \circ w_2 \circ ... \circ w_n | w_1,...w_n \in A$
$$ \chi_{M_2}(w) = \begin{cases} wahr, & \text{wenn } w_1 == a;\\ falsch, & \text{sonst} \end{cases} $$
Anzahl berechenbarer charakteristischer Funktionen
Da die Potenzmenge von $A^*$ überabzählbar unendlich ist, gibt es überabzählbar unendlich viele charakteristische Funktionen (eine für jede Teilmenge). Davon sind nicht alle berechenbar (ein Gegenbeispiel reicht).
Aufzählbarkeit
Eine Menge $M \subseteq A^*$ heißt aufzählbar, wenn es entweder eine total berechenbare surjektive Funktion $f : \N \rightarrow M$ gibt, oder es gilt $M=\emptyset$ Man nennt f eine Aufzählprozedur oder ein Aufzählverfahren von M. Sehr vereinfacht : aufzählbar = abzählbar + berechenbar
Somit muss für den Beweis der Aufzählbarkeit eine entsprechende Funktion $f$ gefunden werden.
Menge der geraden Zahlen G
z.z. Die Menge $G = \{g | g=2n , n \in \N\}$ ist aufzählbar.
Das Aufzählverfahren ergibt sich bereits aus der Definition von $G$.
$f(n) = 2n$
Menge der Primzahlen
$ f(n) = \begin{cases} n, & \text{wenn x eine Primzahl ist} ;\\ 2, & \text{sonst} \end{cases} $
$A^*$
Aufbauschema:
Aufbauprozedur:
jede endliche Menge
Per Definition ist jede endliche Menge abzählbar. Weiterhin gibt es für jede endliche Menge M eine surjektive total berechenbare Funktion f, mit f : N -> M.
Menge G der Gitterpunkte
???? (0,0),(0,1),...
Geben Sie eine Funktion f an, die N bijektiv auf G abbildet. 2 Definieren Sie eine Ordnungsrelation p < in G . 3 Geben Sie eine Funktion k zur Berechnung der Platznummer k(x, y ) des betrachteten Gitterpunktes (x, y ) an. 4 Geben Sie eine Aufz ̈ahlprozedur f ̈ ur G an und begr ̈ unden Sie deren Berechenbarkeit.
Semi Entscheidbarkeit
Halteproblem
Sei $A$ die Menge aller Algorithmen, dann gibt es eine Funktion $\chi'_A$ die wahr zurückgibt, wenn ein Algorithmus terminiert.
$$ \chi'_{A}(a) = \begin{cases} wahr, & \text{wenn a terminiert};\\ \bot, & \text{sonst} \end{cases} $$
FIBS
Aufzählfunktion $\fib(n) = \begin{cases} 1, & \text{wenn n==1 oder n==0};\\ fib(n-1)*fib(n-2), & \text{sonst} \end{cases} $
FIBS Entscheidbar? $$ \chi'_{FIBS}(f) = \begin{cases} wahr, & \text{wenn f in FIBS};\\ falsch, & \text{sonst} \end{cases} $$
Die Menge ist entscheidbar, da die Charakteristische Funktion berechenbar ist.
Aus der Entscheidbarkeit folgt die semi Entscheidbarkeit.
Quadratzahlen
Aufzählfunktion
$f(n)=n^2$
$ \chi_{QZ}(n) = \begin{cases} wahr, & \text{wenn } sqrt(n) \in \N;\\ falsch, & \text{sonst} \end{cases} $
Wörter, die mit a beginnen
Aus Entscheidbarkeit folgt die Semi Entscheidbarkeit.
Vereinigung
Definieren Sie die Menge der geraden Zahlen (Zahlwörter) und die der ungeraden Zahlen (Zahlwörter) und veranlassen Sie das ProgrammingWiki 30 Elemente der Vereinigungsmenge auszugeben.
