BuK/IIm10/BuK-Kreativaufgabe04 G2

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
<language>Scheme</language>
<language>Scheme</language>
<language>Scheme</language>
=Zeitbeschränkte Prozesse mit Engines=
<code id="4dac8619e2872" hidden>
;engine.ss
;wortmenge.ss

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

;g: N-->M , g zählt M auf 
(define g      ; verwendet Alphabet A als freie Variable!!
  (lambda (i)
    (let* ((s (if (< i 2) 1 (ceiling (/ (log i)(log (length A))))))
           (A*-bis-stufe (wortmenge-bis-stufe s A)))
      (list-ref A*-bis-stufe i))))
</code>
Folgender '''Satz''' soll auf dieser Seite mittels Scheme-Engines dargestellt werden:

: Wenn ein Menge M semi-entscheidbar ist, dann ist sie aufzählbar.

Die Aufzählbarkeit einer Menge M wird hier nicht dargestellt.

Aus den ersten Teil des Satzes ''M ist semi-entscheidbar'' kann man folgenden Schluss ziehen:

Es existiert eine Funktion 
<math>
\chi_M '(w)=\begin{cases}
true, \text{wenn }w \in M \\
n.d., sonst
\end{cases}
</math>.

Die Funktion, die für den Beweis erstellt werden muss ist folgend definiert:

<math>
f(i)=\begin{cases}
g(i),\text{wenn } \chi_M '(g(i))\\
a \in M, \text{sonst}
\end{cases}
</math>

Wobei <math>g: \mathbb{N}_0 \rightarrow A^*</math>.
Für das Beispiel wird die Menge mit <math>M=\{a, b, c\}</math> definiert.

Diese Funktion ist partiell berechenbar, d.h. es gibt Eingabeparameter für die <math>\chi_M '</math> stoppt, und welche für die die Funktion nicht stoppt.
Genau diese Wörter, welche nicht in der Menge M enthalten sind, stellen ein Problem dar, da <math>\chi_M '</math> nicht terminiert und ewig läuft.

Die Idee zur Lösung besteht darin, dass man der Prozedur eine gewisse Taktrate vorgibt, wie lange der Berechnungsprozess dauern darf, oder besser gesagt, für jeden Eingabeparameter wird die Funktion nur ein Takt bearbeitet und erst dann für jeden Parameter einen weiteren Takt. 
Somit werden Wörter <math>w \in M</math> innerhalb von "kurzer Zeit" (hier: innerhalb weniger Sekunden) berechnet.

Hier die Prozedur von <math>\chi_M '</math> in Scheme:
<code id="4dac794088b34">
(define fi
  (lambda (w)
    (if (chi-strich? w) 
        w
        "a");
    ))
</code>

<run id="4dac85733b9dd">(chi-strich? "aaa")</run>
<run id="4dac85733bafb">;(chi-strich? "afaa")</run>

Die Funktion kann als Engine implementiert werden:
<code id="4dac85733b734">
(define fi-engine 
  (make-engine (lambda ()(fi "ab"))))
</code>

Die Engine in Scheme benötigt folgende Aufrufparameter:

(1) Anzahl der Takte (die für Berechnung zur Verfügung gestellt werden)

(2) Eine Erfolgs-Prozedur
In demFall wird die Zeit und das Ergebnis als Liste ausgegeben.

(3) Eine Misserfolgs-Prozedur
Wenn die vorgegebene Zeit überschritten ist, wird ''expired'' ausgegeben. 

<code id="4dac85733b7e5">
(define zeitfenster 400);int

(define fi-erfolg
   (lambda (restzeit resultat)
    (list restzeit resultat)))

(define fi-kein-erfolg
  (lambda (restaufgabe)
     'expired!))
</code>

Die Erfolgsprozedur liefert die Restzeit (Anzahl der Takte welche nicht zur Berechnung nötig gewesen sind) und das Ergebnis der Berechnung.

Bei einem Misserfolg wird die (vollständige) Engine gespeichert. Diese kann dazu verwendet werden um später die Berechnung forzusetzen, d.h. weitere Takte werden zur Verfügung gestellt.

Nun folgt der Aufruf mit dem Wort "ab":
<run id="4dac85733bb66">
(fi-engine      
    zeitfenster fi-erfolg fi-kein-erfolg)
</run>

Durch die Engine können wir die Prozedur auch mit Wörtern die nicht Element der Menge sind aufrufen und diese stoppt nach endlicher Zeit.
<code id="4dac85733b86a">
(define fi-engine (make-engine (lambda ()(fi "abx"))))
</code>
<run id="4dac85733bbf3">
(fi-engine      zeitfenster fi-erfolg fi-kein-erfolg)
</run>

Bisher liefert die Misserfolgs-Prozedur eine Meldung. Durch eine andere Definition erreichen wir, dass bei einem erneuten Aufruf die Bwerechnung forgesetzt wird:
<code id="4dac85733b8d6">
(define fi-kein-erfolg-2
  (lambda (restaufgabe)
    (set! fi-engine restaufgabe)
     'expired!))
</code>
Um das zu verdeutlichen, werden wir nun den Aufruf der Engine mit dem Wort "aabbc" starten. Durch mehrmaliges Ausführen wird die Berechnung bis zum Ergebnis weitergeführt, aber nur falls in endlicher Vorgabe, vorhanden.   
<code id="4dac85733b946">
(define fi-engine (make-engine (lambda ()(fi "aabbc"))))
</code> 
<run id="4dac85733bc7d">
(fi-engine      zeitfenster fi-erfolg fi-kein-erfolg-2)
</run>