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.

==== 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}
$$

==== 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>

=== 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="4f968e5d40cf7">
(define A '(#\a #\b #\c))
</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.

=== Schritt 4 ===

Einsetzen eines Timer-Systems.

=== Schritt 5 ===

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