BuK/IIm14/Studenten/s3rozoek/Uebung3

Wiki-Quelltext dieser Seite.

<language>Javascript</language>
= Ü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}
$$

<code id="552e54cde090f">
function chiM1(wort){
if(wort=="aaa"||wort=="aba"||wort=="aab"||wort=="baa"||wort=="bab"||wort=="abb"||wort=="bbb"){return true;}
else{return false;}
}
</code>

<run id="552e54cde0985">
chiM1("aaa")
</run>


=== 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}
$$

<code id="552e554c46082">
function chiM2(wort){
if(wort.charAt(0)=="a"){return true;}
else{return false;}
}
</code>

<run id="552e554c460f9">
chiM2("abbbbabababababba")
</run>


== 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) = 2n$

=== Menge der Primzahlen ===


$ f(n) = \begin{cases}
n, & \text{wenn x eine Primzahl ist} ;\\
2, & \text{sonst}
\end{cases} $

=== $A^*$ ===
Aufbauschema:
[[Bild:Rzoeke_ASternAufbauschema.png]]

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.


=== Quadratzahlen ===

=== Wörter, die mit a beginnen ===