Halteproblem

Aufgabenstellung

Spielen Sie die Betrachtungen zum Halteproblem (s. Vorlesung) mit Scheme-Prozeduren nach.

Hinweis: Definieren Sie ggf. auch eine Prozedur haelt-tricky?, die \#t zurück gibt, wenn das betrachtete Programm P ein Ergebnis berechnet, und \#f, wenn die Berechnung in einer gewissen Zeit T zu keinem Ergebnis führt. Verwenden Sie zeitbeschränkte Berechnungen, deren Implementierungidee einige Kreativität erfordert.

Lösung

Beweise

Aufgabenstellung

Lösung

Bijektive Funktion

Lösung