BuK/IIm12/Studenten/sifedeut/uebung3
Aus ProgrammingWiki
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>
> (chi "bin_in_M")
#t
> (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 (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).
==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.
==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>
<language>Scheme</language>
<language>Scheme</language>
<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="5164740b24f7f" hidden>
(define stream-car car)
(define stream-cdr
(lambda (stm)
(force (cdr stm))))
(define-syntax stream-cons
(syntax-rules ()
((_ head tail) (cons head (delay tail)))))
(define stream-item
(lambda (str k)
(if (= k 0)
(stream-car str)
(stream-item (stream-cdr str) (- k 1)))))
(define stream->list
(lambda (str n)
(if (<= n 0)
'()
(cons
(stream-car str)
(stream->list (stream-cdr str) (- n 1))))))
(define print-stream
(lambda (stm n)
(cond
((<= n 0) (display "...\n"))
(else
(display (stream-car stm))
(display ", ")
(print-stream (stream-cdr stm) (- n 1))))))
(define stream-map
(lambda (stm proc)
(stream-cons
(proc (string->number (stream-car stm)))
(stream-map (stream-cdr stm) proc))))
(define natstream
(lambda (start)
(stream-cons (number->string start) (natstream (+ 1 start)))))
(define natzahlstream (stream-cons (number->string 0) (natstream 1)))
</code>
<code id="51646bc0d522b">
; Die Funktion f1, die die Menge der geraden Zahlen berechnet
(define f1
(lambda (i)
(number->string(* 2 i))))
; Die Funktion f2, die die Menge der ungeraden Zahlen berechnet
(define f2
(lambda (i)
(number->string(+ (* 2 i) 1))))
;einen Mengengenerator erstellen
(define generiere_aufzaehlbare_menge
(lambda (f)
(stream-map natzahlstream f)))
(define M1 (generiere_aufzaehlbare_menge f1))
(define M2 (generiere_aufzaehlbare_menge f2))
</code>
<run id="51646c4d8077b">
(f1 1)
</run>