BuK/IIm12/Studenten/s3erjaeh

Wiki-Quelltext dieser Seite.

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