Kreativaufgabe3

Aus ProgrammingWiki

< BuK < IIm11 < Studenten < sistsche

Archivierte Version vom 2012-04-03T17:41:47+00:00. Aktuelle Version

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 semi-entscheidbaren Methode, die wahr liefert, wenn w \in M_{1} \cap M_{2}\\ Frage: Darf man eine semi-entscheidbare Funktion anstatt einer Aufzählprozedur benutzen???

Antwort:

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.

Wie könnte die Methode aussehen??

(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))

(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)

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 = |A| 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).

Kreativaufgabe3

Suche