BuK-KA-Zeitbeschränkte-Prozesse

Aus ProgrammingWiki

Inhaltsverzeichnis

1 Aufgabenstellung
2 Umsetzung

Aufgabenstellung

Implementieren Sie die im Beweis definierte Aufzählfunktion für M \subseteq \text{ A*} unter Verwendung der Cantorschen Paarungsfunktion. Wählen Sie im Fallbeispiel A = \{a,b,c\}, g: \N \mapsto A^* und M = \{w |w \in A^* \text{ und } w \text{ enthält Fibonacci-zahlig viele} "b's"\}.

Machen Sie bei der Konstruktion von \chi^'_M nur von der Semi-Entscheidbarkeit der Menge der Fibonacci-Zahlen Gebrauch, obwohl doch deren Entscheidbarkeit durch Beschränkung des Suchraumes gegeben ist.

Hinweis: Sie benötigen keine engines. Das einfache Timer-System reicht aus. Um Prozesse, die in eine bestimmten Vorgabezeit nicht terminieren, auch wirklich abbrechen zu können, benötigen Sie Continuations (Sprachelement call/cc).

(define end #f)
(call/cc (lambda (cont) (set! end cont)))

(define start-timer #f)
(define stop-timer #f)
(define decrement-timer #f)

(let ([clock 0] [handler #f])
  (set! start-timer
        (lambda (ticks new-handler)
          (set! handler new-handler)
          (set! clock ticks)))
  (set! stop-timer
        (lambda ()
          (let ([time-left clock])
            (set! clock 0)
            time-left)))
  (set! decrement-timer
        (lambda ()  
          (when (> clock 0)
            (set! clock (- clock 1))
            (when (= clock 0) (handler))))))

(define fib
  (lambda (n)  
    (decrement-timer)
    (cond
      ((= n 0) 0)
      ((= n 1) 1)
      (else
       (+ (fib (- n 1)) (fib (- n 2)))))))

(define cantor-paar
  (lambda (x y)
    (+ (/ (* (+ x y) (+ x y 1)) 2) y)))

(define wortmenge_Zeichenlaenge
  (lambda (n alphabet)
    (if (= n 0)
        '("")
        (apply
         append
         (map 
          (lambda (zeichen)
            (map
             (lambda (wort)(string-append (string zeichen) wort))
             (wortmenge_Zeichenlaenge (- n 1) alphabet)))
          alphabet)))))

(define wortmenge
  (lambda (n alphabet)
    (if (= n 0)
        (wortmenge_Zeichenlaenge 0 alphabet)
        (append 
         (wortmenge (- n 1) alphabet)
         (wortmenge_Zeichenlaenge n alphabet)))))

(define A '(#\a #\b #\c))

(define g 
  (lambda (i)
    (let* ((n (if (< i 2) 1 (ceiling (/ (log i)(log (length A))))))
           (wortmenge-n (wortmenge n A)))
      (list-ref wortmenge-n i))))

(define f
  (lambda (z)
    (let* ((x (getXCantorPaar z))
           (y (getYCantorPaar z))
           (fibwort (g x)))
      (start-timer y (lambda () (end "b")))
      (when (chi-strich-m fibwort)
          fibwort))))

(define chi-strich-m
  (lambda (w)
    (letrec
        ((helper
          (lambda (i)   
            (decrement-timer)
            (if (= (countB w) (fib i))
                #t
                (helper (+ i 1))))))
      (helper 0))))

(define countB
  (lambda (w)
   (letrec
        ((helper
          (lambda (chars)
            (cond
              ((null? chars) 0)
              ((char=? (car chars) #\b)(+ 1 (helper (cdr chars))))
              (else
               (helper (cdr chars)))))))
      (helper (string->list w)))))

(define getXCantorPaar
  (lambda (z)
    (let* (( w (floor (/ (- (sqrt (+ (* 8 z) 1)) 1) 2)))
          ( t (/ (* w (+ w 1)) 2))
          ( y (- z t)))
      (inexact->exact (- w y)))))

(define getYCantorPaar
  (lambda (z)
    (let* (( w (floor (/ (- (sqrt (+ (* 8 z) 1)) 1) 2)))
           (t (/ (* w (+ w 1)) 2)))
      (inexact->exact (- z t)))))

Umsetzung

Schritt 1

Implementieren Sie die im Beweis definierte Aufzählfunktion für M \subseteq \text{ A*} unter Verwendung der Cantorschen Paarungsfunktion.

Definition der Cantorschen Paarungsfunktion

\begin{array}{c|cccccc} x\backslash y & 0 & 1 & 2 & 3 & 4 & \dots\\\hline 0 & 0 & 2 & 5 & 9 & 14 & \dots \\ 1 & 1 & 4 & 8 & 13 & \dots & \\ 2 & 3 & 7 & 12 & \dots & & \\ 3 & 6 & 11 & \dots & & & \\ 4 & 10 & \vdots & \vdots & \vdots & \vdots & \end{array}

x bestimmt das x-te Element, also g(x)=w_x, in der Aufzählung von A^* durch g. Und y bestimmt die zur Berechnung von \chi^'_M(w_x) bereitgestellten Zeiteinheiten (Takte, ticks) - entweder für die Berechnung ausreichend oder Abbruch nach Zeit y.

z = \pi(x,y) = \frac{(x+y)(x+y+1)}{2} + y

(define cantor-paar
  (lambda (x y)
    (+ (/ (* (+ x y) (+ x y 1)) 2) y)))

(cantor-paar 286 5)

Um die beiden natürlichen Zahlen x und y aus z zu gewinnen, ist als erstes w = \left\lfloor \frac{\sqrt{8z+1}-1}{2} \right\rfloor zu berechnen. Dann ergeben sich t = \frac{w(w+1)}{2} und y = z -t sowie

x = w - y

(define getXCantorPaar
  (lambda (z)
    (let* (( w (floor (/ (- (sqrt (+ (* 8 z) 1)) 1) 2)))
          ( t (/ (* w (+ w 1)) 2))
          ( y (- z t)))
      (inexact->exact (- w y)))))

(define getYCantorPaar
  (lambda (z)
    (let* (( w (floor (/ (- (sqrt (+ (* 8 z) 1)) 1) 2)))
           (t (/ (* w (+ w 1)) 2)))
      (inexact->exact (- z t)))))

(getXCantorPaar 42491)

(getYCantorPaar 42491)

Aufzählfunktion f für M \subseteq \text{ A*}

f(z) = \begin{cases} g(x); & \text{wenn } \chi^{'}_{M}(g(x))=\text{ wahr innerhalb von Zeit y};\\ b; & \text{wenn Proz. für } \chi^{'}_{M}(g(x)) \text{ innerhalb von y ohne Ergebnis} \end{cases} b \in M

(define f
  (lambda (z)
    (let* ((x (getXCantorPaar z))
           (y (getYCantorPaar z))
           (fibwort (g x)))
      (start-timer y (lambda () (end "b")))
      (when (chi-strich-m fibwort)
          fibwort))))

(f (cantor-paar 286 5))

Schritt 2

Wählen Sie im Fallbeispiel A = \{a,b,c\}, g: \N \mapsto A^* und M = \{w |w \in A^* \text{ und } w \text{ enthält Fibonacci-zahlig viele} "b's"\}.

Alphabet A

(define A '(#\a #\b #\c))

Berechnung einer Fibonacci-Zahl

(define fib
  (lambda (n)  
    (decrement-timer)
    (cond
      ((= n 0) 0)
      ((= n 1) 1)
      (else
       (+ (fib (- n 1)) (fib (- n 2)))))))

Wörter der Länge n

Ermittlung der Wörter mit der Länge n, aus der Wortmenge A^*.

(define wortmenge_Zeichenlaenge
  (lambda (n alphabet)
    (if (= n 0)
        '("")
        (apply
         append
         (map 
          (lambda (zeichen)
            (map
             (lambda (wort)(string-append (string zeichen) wort))
             (wortmenge_Zeichenlaenge (- n 1) alphabet)))
          alphabet)))))

(wortmenge_Zeichenlaenge 6 A)

Wörter bis zur Länge n

Ermittlung der Wörter, aus der Wortmenge A^*, bis zur Länge n.

(define wortmenge
  (lambda (n alphabet)
    (if (= n 0)
        (wortmenge_Zeichenlaenge 0 alphabet)
        (append 
         (wortmenge (- n 1) alphabet)
         (wortmenge_Zeichenlaenge n alphabet)))))

(wortmenge 6 A)

Aufzählfunktion g(x)

(define g 
  (lambda (i)
    (let* ((n (if (< i 2) 1 (ceiling (/ (log i)(log (length A))))))
           (wortmenge-n (wortmenge n A)))
      (list-ref wortmenge-n i))))

(g 286)

Schritt 3

Anzahl von b's

(define countB
  (lambda (w)
   (letrec
        ((helper
          (lambda (chars)
            (cond
              ((null? chars) 0)
              ((char=? (car chars) #\b)(+ 1 (helper (cdr chars))))
              (else
               (helper (cdr chars)))))))
      (helper (string->list w)))))

(countB "caaba")

Semi-Entscheidbarkeit

(define chi-strich-m
  (lambda (w)
    (letrec
        ((helper
          (lambda (i)   
            (decrement-timer)
            (if (= (countB w) (fib i))
                #t
                (helper (+ i 1))))))
      (helper 0))))

(chi-strich-m "caaba")

(start-timer 40 (lambda () (end "b")))
(chi-strich-m "caabbbba")

Schritt 4

Einsetzen eines Timer-Systems

(define start-timer #f)
(define stop-timer #f)
(define decrement-timer #f)

(let ([clock 0] [handler #f])
  (set! start-timer
        (lambda (ticks new-handler)
          (set! handler new-handler)
          (set! clock ticks)))
  (set! stop-timer
        (lambda ()
          (let ([time-left clock])
            (set! clock 0)
            time-left)))
  (set! decrement-timer
        (lambda ()  
          (when (> clock 0)
            (set! clock (- clock 1))
            (when (= clock 0) (handler))))))

Schritt 5

Um Prozesse, die in eine bestimmten Vorgabezeit nicht terminieren, auch wirklich abbrechen zu können, benötigen Sie Continuations (Sprachelement call/cc).

Continuations

(define end #f) 
(call/cc (lambda (cont) (set! end cont)))

Beispiel Timer-System

(start-timer 250 (lambda () (end "end time")))
(fib 10)