Uebung3
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
????
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) = 2nMenge der Primzahlen
$ f(n) = \begin{cases} n, & \text{wenn x eine Primzahl ist} ;\\ 2, & \text{sonst} \end{cases} $
A^*
Aufbauschema:
Aufbauprozedur: ??????????
jede endliche Menge
??
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.