uebung3
Aus ProgrammingWiki
Inhaltsverzeichnis |
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 relativ entscheidbar zur Menge $M_2 (M_1,M_2\subseteq A^*)$, wenn die charakteristische Funktion $\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: total berechenbar) Funktion ist. D.h. man kann für jedes 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) entscheidbar, 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) chi gibt, die für jedes Wort $w$ aus $A^*$ nach endlicher Zeit stoppt und entweder #t ($w\in M$) oder #f ($w \not\in M$) ausgibt.
> (chi "bin_in_M") #t > (chi "bin_nicht_in_M") #f
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 Aufzählprozedur oder ein Aufzählverfahren 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 semi-entscheidbar, 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 (Deutschmann, Horbach)
Wie viele berechenbare charakteristische Funktionen gibt es?
Hinweis: Potenzmenge unendlicher Mengen
$\mathscr{P}(A^*)$ besitzt überabzählbar unendlich viele Mengen
Die Teilmengen von $A^*$ sind selbst endlich oder abzählbar unendlich.
Deshalb gibt es überabzählbar unendlich viele charakteristische Funktionen $\chi_M$.
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).
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 a's und b's bestehen und mit a beginnen.
$A^*=\{a,b\}^*$ und $M\subset A^*=\{w=aw'| w'\in A^*\}$
Aufgabe 3 (Deutschmann, Horbach)
Zeigen Sie, dass die Menge der geraden Zahlen G eine aufzählbare Menge ist.
Wdh: Aufzählbar = abzählbar + berechenbar
abzählbar: Für die Menge der geraden Zahlen $G$ gilt: $G\subset\Z$, die abzählbar unendlich sind Beweis
berechenbar: Es existiert ein Algorithmus, der für die Funktion $f(x)$ für jedes $x \in D_f$ den zugehörigen Funktionswert $f(x)$ ermittelt
$f(x)=\begin{cases}-i & \text{, wenn i gerade}\\i+1 & \text{, wenn i ungerade}\end{cases}$
Aufgabe 4
Zeigen Sie, dass die Menge der Primzahlen P aufzählbar ist.
Primzahlen sind abzählbar unendlich Beweis.
Aufzählbar = abzählbar + berechenbar
Aufzählbar:
- es gibt eine Aufzählprozedur $h:\N\mapsto A^*$
- total berechenbar
- mind. surjektiv
Berechenbar = "Es existiert eine implementierte Funktion (also eine Prozedur)"
Für die Aufzählbarkeit fehlt noch ein Algorithmus für eine Funktion, welche die Primzahlen berechnen kann.
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 $M$ aufzählbar ist.
Lösung:
Aufzählbar = abzählbar + berechenbar
Laut Definition heißt eine Menge $M$ endlich, wenn es eine natürliche Zahl $n$ gibt, sodass eine Bijektion zwischen $M$ und der Menge aller natürlichen Zahlen kleiner als $n$ existiert, d.h. jede endliche Menge ist abzählbar.
Eine Menge $M$ heißt (rekursiv) aufzählbar wenn es entweder eine total berechenbare surjektive Funktion $f:N \mapsto M$ gibt, oder es gilt $M = \emptyset$. Man nennt $f$ eine Aufzählprozedur oder ein Aufzählverfahren von M.
Es gibt eine Funktion $f$, die als Eingabe die natürlichen Zahlen $\N$ nimmt und auf jedes Element der endlichen Menge $M$ abbildet. $f$ ist berechenbar, da es eine total berechenbare surjektive Funktion $f : \N \mapsto M$ gibt. Es wird der Reihe nach jedes Element aus $\N$ einem Element aus $M$ zugeordnet. Ist $f$ surjektiv, können die restlichen Elemente aus $\N$ auf ein beliebiges Element von $M$ abgebildet werden. Somit ist $f$ surjektiv, total und berechenbar.
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.
Lösung:
zu 1. $$g(z) = \begin{cases} (x,y) & \text{, mit } x=w-y,\\ & y = z - t \text{, wobei }\\\\ & w = \lfloor \frac{\sqrt{8z+1}-1}{2}\rfloor,\\\\ & t = \frac{w(w+1)}{2} \end{cases} \text{, mit }z\in\N$$
zu 2.
Die Paare sollen nach dem aufsteigendem Funktionswert der Funktion $\pi (x,y) = \frac{(x + y)(x + y + 1)}{2} + y$ geordnet werden.
zu 3.
Die Funktion aus 2. sei $k(x,y)$.
zu 4.
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.
Per Definition ist eine Menge $M$ aufzählbar, wenn es eine totale berechenbare Prozedur $f$ gibt, welche die Menge $\N$ auf die Menge $M$ abbildet. $M$ ist hier die Menge der Fibonacci-Zahlwörter.
Überarbeiten!!! Die Aufzählprozedur lautet wie folgt: $$f(n) = \begin{cases} g(n), & \text{wenn } g(n) \in \text{ M};\\ 0, & sonst. \end{cases}$$
Für $g(n)$ gilt: $$g(n) = \begin{cases} 0, & \text{wenn } n=0;\\ 1, & \text{wenn } n=1;\\ (n-1) + (n-2), & sonst. \end{cases}$$
Für beide, also für $f$ und $g$, lassen sich entsprechende Scheme Ausdrücke angeben:
Es wird noch eine charakteristische Funktion $\chi$ benötigt.
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.
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}$
