BuK/IIm12/Studenten/sifedeut/uebung3

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
=Theorie=
Im Gegensatz zu Funktionen sind Mengen nicht ''berechenbar'', sondern ''entscheidbar''. Man spricht bei '''Mengen''' von '''Entscheidbarkeit'''

==relativ entscheidbare Mengen==
Eine Menge $M_1$ ist <b>relativ entscheidbar</b> zur Menge $M_2 (M_1,M_2\subseteq A^*)$, wenn die <b>charakteristische Funktion</b> $\chi_{M_1,M_2}$ mit

$\chi_{M_1,M_2}(w)=\begin{cases}wahr & \text{,wenn } w\in M_1\\falsch & \text{, wenn } w\in M_2\setminus M_1\end{cases}$

eine totale und berechenbare (kurz: <b>total berechenbar</b>) Funktion ist. D.h. man kann für <u>jedes</u> Element der Menge $M_2$ sagen, ob es sich um ein Element der  Menge $M_1$ handelt oder nicht.

==(absolut) entscheidbare Mengen==
Eine Menge $M\subseteq A^*$ ist (absolut) <b>entscheidbar</b>, wenn $M$ zu $A^*$ relativ entscheidbar ist, d.h. wenn $\chi_{M,A^*}$, kurz $\chi_{M}$, mit

$\chi_{M}(w)=\begin{cases}wahr & \text{,wenn } w\in M\\falsch & \text{, wenn } w\in A^*\setminus M\end{cases}$

eine total berechenbare Funktion ist.

Anders gesagt: $M$ ist entscheidbar, wenn es eine Prozedur (eine in einer beliebigen Programmiersprache implementierte Funktion) <tt>chi</tt> gibt, die für jedes Wort $w$ aus $A^*$ nach endlicher Zeit stoppt und entweder <tt>#t</tt> ($w\in M$) oder <tt>#f</tt> ($w \not\in M$) ausgibt.

 <nowiki>
 &gt; (chi "bin_in_M")
 #t
 &gt; (chi "bin_nicht_in_M")
 #f</nowiki>

==Aufzählbar==
Eine Menge $M\subseteq A^*$ heißt (rekursiv) aufzählbar, wenn es entweder eine total berechbare surjektive Funktion $f\colon\N\mapsto M$ gibt, oder es gilt $M = \emptyset$. Man nennt $f$ eine <b>Aufzählprozedur</b> oder ein <b>Aufzählverfahren</b> von $M$.

Stark vereinfacht: aufzählbar $=$ abzählbar + berechenbar

==von Aufzählbar zu Entscheidbar==
Im allgemeinen Fall sichert die Aufzählbarkeit einer Menge lediglich deren Semi-Entscheidbarkeit.

Eine Menge $M\subseteq A^*$ ist <b>semi-entscheidbar</b>, wenn die partielle (semi-charakteristische) Funktion $\chi'_M \colon A^*\mapsto\{\text{wahr}\}$ mit

$\chi'_M(w)=\begin{cases}wahr & \text{, wenn }w\in M\\\perp & \text{, sonst}\end{cases}$

berechenbar ist.

=Übungsaufgaben zur Entscheidbarkeit und Aufzählbarkeit=
==Aufgabe 1==
Wie viele berechenbare charakteristische Funktionen gibt es?

Hinweis: Potenzmenge unendlicher Mengen
==Aufgabe 2==
Zeigen Sie, dass die beiden Mengen aus den Beispielen entscheidbar sind. Schreiben Sie je eine entsprechende Prozedur für die jeweilige charakteristische Funktion (ProgrammingWiki).

==Aufgabe 3==
Zeigen Sie, dass die Menge der geraden Zahlen G eine aufzählbare Menge ist.

'''Beispiel 1''': endliche Menge

$A^*=\{a,b\}^*$ und $M\subset A^*=\{w | w\in A^* \text{und } \left|w\right|=3\}$

'''Beispiel 2''': abzählbar unendliche Menge

$M$ ist die Menge aller Wörter, die aus beliebig vielen <tt>a</tt>'s und <tt>b</tt>'s bestehen und mit <tt>a</tt> beginnen. 

$A^*=\{a,b\}^*$ und $M\subset A^*=\{w=aw'| w'\in A^*\}$

==Aufgabe 4==
Zeigen Sie, dass die Menge der Primzahlen P aufzählbar ist.

==Aufgabe 5==
Wir wissen, dass $A^*$ eine abzählbar unendliche Menge ist. Zeigen Sie, dass $A^*$ auch aufzählbar ist.

Hinweis: Hierzu ist es notwendig ein Aufbauschema für $A^*$ zu entwerfen und anschließend eine Prozedur dafür zu implementieren.

==Aufgabe 6==
Zeigen Sie, dass jede endliche Menge aufzählbar ist.

==Aufgabe 7==
Die Menge $G$ der Gitterpunkte $(0,0),(0,1),...$ einer x-y-Ebene ist aufzählbar.
# Geben Sie eine Funktion f an, die $\N$ bijektiv auf $G$ abbildet.
# Definieren Sie eine Ordnungsrelation $p<$ in G
# Geben Sie eine Funktion k zur Berechnung der Platznummer $k(x,y)$ des betrachteten Gitterpunktes $(x,y)$ an.
# Geben Sie eine Aufzählprozedur für $G$ an und begründen Sie deren Berechenbarkeit.

==Aufgabe 8==
Das Halteproblem ist semi-entscheidbar. Beweisen Sie diese Aussage.

==Aufgabe 9==
Geben Sie für die Menge $FIBS$ der Fibonacci-Zahlwörter eine Aufzählfunktion an und begründen Sie deren Berechenbarkeit. Weisen Sie nach, dass $FIBS$ sogar entscheidbar ist.

==Aufgabe 10==
Übertragen Sie die vorhergehende Übungsaufgabe sinngemäß auf die Menge der Quadratzahlen $QZ = \{n^2 | n\in\N\}$.

==Aufgabe 11==
Weisen Sie nach, dass die Menge $M$ aller "Wörter" aus $\{a,b\}^*$, die mit a beginnen, semi-entscheidbar ist.

<language>Scheme</language>
==Aufgabe 12==
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.

$M_1$ ist die Menge der geraden Zahlen

$f_1(i)=string(2i)$

$M_2$ ist die Menge der ungeraden Zahlen

$f_2(i)=string(2i+1)$

Für die Vereinigung der beiden Mengen kann die folgende Funktion genommen werden:

$h(i)=\begin{cases}f_1(\frac{i}{2}) & \text{, wenn }i\text{ gerade}\\f_2(\frac{i-1}{2}) & \text{, wenn }i\text{ ungerade}\end{cases}$
<code id="516469a511675">
(define nat-stream 
    )
</code>