Kreativaufgabe Zeitbeschränkte Prozesse (Kretschmer, Schumann)

Aus ProgrammingWiki

Inhaltsverzeichnis

1 Aufgabenstellung
2 Lösung

Autoren: Tom Schumann; Hannes Kretschmer

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.

Lösung

Abbildung der Natürlichen Zahlen

Menge der Fibonacci-Wörter

Cantorsche Paarungsfunktion

g: \N \mapsto A^*

Aufzählfunktion

Zeitbegrenzung

class ChiThread(Thread):
    def __init__(self, w):
        super(ChiThread, self).__init__()
        self.word = w
        self.result = False
        self.stoprequest = threading.Event()

    def join(self, timeout=None):
        self.stoprequest.set()
        super(ChiThread, self).join(timeout)

    def run(self):
        self.result = chi_strich_m(self.word)

    def return_result(self):
        return self.result