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:\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
Ü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.
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.