BuK/IIm11/Studenten/sistsche/Kreativaufgabe3
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
Gegeben:
$ M_{1},M_{2} \subseteq A^{*} \text{ mit }
f: \N \rightarrow M_{1} \text{ und } g: \N \rightarrow M_{2} $
Gesucht:
$ M_{1} \cap M_{2} $ zweier aufzählbar unendliche Mengen $M_{1},M_{2}\subseteq A^{*}$ ist eine aufzählbare Menge.
aufzählbar = abzählbare und berechenbare Lösung:
(1) $ M_{1} \cap M_{2} = \emptyset $
Beispiel.:
$ M_{1} = \text{ungeraden Zahlen} $
$ M_{2} = \text{geraden Zahlen} $
$ M_{1} \cap M_{2} = \emptyset \square $
(2)
Lösungsansatz: Konstruieren einer Methode, die alle Elemente der Schnittmenge geordnet liefert.Dazu notwendig ist eine semi-entscheidbare Funktion, die w als Ergebnis liefert, wenn $ w \in M_{1} \cap M_{2}$, , wobei $w = f(i) = g(j)$.
Wir konstruieren eine semi-entscheidbare Methode, die Schritt für Schritt mithilfe der Aufzählungsfunktion $f(n)$ ein Element aus der aufzählbaren Menge $M$ erzeugt und mit dem übergebenen $w$ vergleicht. Dabei liefert sie $wahr$, wenn $w = f(n)$ und ist sonst nicht definiert.
$$\chi M(w)=\begin{cases}
wahr, \text{ wenn } f(n) = w \text{ für alle } n \in \N \\
\perp, \text{ wenn } f(n) \neq w \text{ für alle } n \in \N
\end{cases}$$
Satz: Wenn $ M \subseteq \N$ aufzählbar ist, so ist M semi-entscheidbar.
'''Fragestellung:''' Wie könnte die Methode aussehen?
<code id="4f7af9c9e5e0b" 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?
(lambda (stm)
(and (pair? stm)(promise? (cdr stm)))))
(define stream-item
(lambda (str nr)
(if(<= nr 0)
(stream-car str)
(stream-item (stream-cdr str) (- nr 1)))))
(define nat-stream-maker
(lambda (start)
(stream-cons start (nat-stream-maker (+ start 1)))))
(define prim?
(lambda (n)
(letrec
((helfer
(lambda (t)
(cond
((> t (sqrt n)) #t)
((= (remainder n t) 0) #f)
(else
(helfer (+ t 2)))))))
(cond
((= n 1) #f)
((= n 2) #t)
((even? n) #f)
(else
(helfer 3))))))
(define print-stream
(lambda (stm n)
(cond
((<= n 0) (display "...\n"))
(else
(display (number->string(stream-car stm)))
(display ", ")
(print-stream (stream-cdr stm) (- n 1))))))
(define stream-map
(lambda (stm proc)
(stream-cons
(proc (stream-car stm))
(stream-map (stream-cdr stm) proc))))
(define stream-filter
(lambda (stm test)
(cond
((test (stream-car stm)) (stream-cons (stream-car stm) (stream-filter (stream-cdr stm) test)))
(else
(stream-filter (stream-cdr stm) test)))))
(define fib-maker
(lambda (a b)
(stream-cons a (fib-maker b (+ a b)))))
</code>
<code id="4f797f955cc29">
(define make-stream-intersect
(lambda (stm1 stm2)
(letrec ((n 0)
(stm1org stm1)
(stm2org stm2)
(stream-intersect-helper
(lambda (stm1 stm2 n)
(cond
((even? n)
(if(stream-contains? (stream-car stm1) stm2org (/ n 2))
(stream-cons (stream-car stm1) (stream-intersect-helper (stream-cdr stm1) stm2 (+ n 1)))
(stream-intersect-helper (stream-cdr stm1) stm2 (+ n 1))))
(else
(if(stream-contains? (stream-car stm2) stm1org (/ (- n 1) 2) )
(stream-cons (stream-car stm2) (stream-intersect-helper stm1 (stream-cdr stm2) (+ n 1)))
(stream-intersect-helper stm1 (stream-cdr stm2) (+ n 1))))))))
(stream-intersect-helper stm1 stm2 n))))
(define stream-contains?
(lambda (item stm n)
(cond
((equal? item (stream-car stm)) #t)
((= n 0 ) #f)
(else (stream-contains? item (stream-cdr stm) (- n 1))))))
(define natstream (nat-stream-maker 0))
(define oddstream (stream-map natstream(lambda (x) (+ 1 (* 2 x)))))
(define primstream (stream-filter natstream prim?))
(define fibstream (fib-maker 0 1))
</code>
<run id="4f797f955cc93">
(display "fibanocci Zahlen\n")
(print-stream fibstream 10)
(display "geraden Zahlen\n")
(print-stream oddstream 10)
(define intersectstream (make-stream-intersect fibstream oddstream))
(display "Schnittmenge Fibanocci und gerade Zahlen\n")
(print-stream intersectstream 10)
</run>
Mithilfe der semi-entscheidbaren Funktion kann man nun überprüfen, ob $w$ in der Schnittmenge liegt
$$h(w)=\begin{cases}
wahr, \text{ wenn } w = g(i) \text{ und } w = f(j) \\
\perp, \text{sonst}
\end{cases}$$
In der oben abgebildeten Scheme-Prozedur werden die ersten n Elemente der Schnittmenge als Resultat geliefert. Um gewährleisten zu können, dass die Funktion nach endlich vielen Schritten entscheidet, ob ein Wort w auch in der anderen (Teil-) Menge vorhanden ist, werden die von den Turing-Maschinen akzeptierten Mengen an Wörtern schrittweise und abwechselnd erweitert. Durch die Schaffung der endlichen Teilmengen kann zumindest in den Zwischenschritten das Terminieren nach $n = |M|$ Schritten gewährleistet werden.
Das Problem der Semi-Entscheidbarkeit besteht jedoch weiterhin, da nicht garantiert werden kann, ob ein n-tes Element existiert und die Funktion nach endlicher Zeit das gewünschte Ergebnis liefern kann (oder eben nicht).
Frage: Darf man eine semi-entscheidbare Funktion anstatt einer Aufzählprozedur benutzen?
Antwort: Semi-entscheidbare Funktion ist aufzählbar:
<code id="4f7b4704bd90b">
(define semi-chi
(lambda (stm wort)
(letrec
((helfer
(lambda (stm)
(if (equal? wort (stream-car stm))
#t
(helfer (stream-cdr stm))))))
(helfer stm))))
(define semi-aufzaehl
(lambda (A* stm)
(if (semi-chi stm (stream-car A*))
(stream-cons (stream-car A*) (semi-aufzaehl (stream-cdr A*) stm))
(semi-aufzaehl (stream-cdr A*) stm))))
</code>
<run id="4f7b4704bd984">
(define natzaehl (semi-aufzaehl natstream natstream))
(print-stream natzaehl 10)
</run>
<run id="4f7b4784b7685">
(define oddzaehl (semi-aufzaehl natstream oddstream))
(print-stream oddzaehl 10)
</run>