uebung3
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.
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 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.
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}