BuK-KA-Zeitbeschränkte-Prozesse

Aus ProgrammingWiki
< BuK < IIm11
Archivierte Version vom 2012-04-23T13:29:40+00:00. Aktuelle Version

Inhaltsverzeichnis

Zeitbeschränkte Prozesse

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