BuK/IIm11/BuK-KA-Zeitbeschränkte-Prozesse

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
== 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'').

== Umsetzung ==

=== Schritt 1: ===

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

<language>Scheme</language>
==== 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};\\
a; & \text{wenn Proz. für } \chi^{'}_{M}(g(x)) \text{ innerhalb von y ohne Ergebnis}
\end{cases}
$$

<code id="4f9691582de84">
(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))))
</code>

==== Definition der Cantorschen Paarungsfunktion ====

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

<code id="4f968e5d40c8e">
(define cantor-paar
  (lambda (x y)
    (+ (/ (* (+ x y) (+ x y 1)) 2) y)))
</code>

<run id="4f9690523e311">(cantor-paar 17 5)</run>

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

<code id="4f968fc1beadf">
(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)))))
</code>

<run id="4f9690917c6cf">(getXCantorPaar 258)</run>
<run id="4f9690917c74f">(getYCantorPaar 258)</run>

<language>Scheme</language>
=== 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:

<code id="4f96928db09f7">
(define A '(#\a #\b #\c))

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

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

=== Schritt 3 ===

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.

<language>Scheme</language>
=== Schritt 4 ===

Einsetzen eines Timer-Systems.

<code id="4f96932f24386">
(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))))))
</code>

=== Schritt 5 ===

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