BuK-KA-Zeitbeschränkte-Prozesse
Aus ProgrammingWiki
Inhaltsverzeichnis |
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.
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
$$
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$
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$$
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
Berechnung einer Fibonacci-Zahl
Wörter der Länge $n$
Ermittlung der Wörter mit der Länge $n$, aus der Wortmenge $A^*$.
Wörter bis zur Länge $n$
Ermittlung der Wörter, aus der Wortmenge $A^*$, bis zur Länge $n$.
Aufzählfunktion $g(x)$
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.
Anzahl von b's
Semi-Entscheidbarkeit
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).
Continuations
