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

1. Zeigen Sie, dass die Menge der rationalen Zahlen abzählbar unendlich ist.
2. Zeigen Sie, dass die Wortmenge A^\ast über A abzählbar unendlich ist.
3. Zeigen Sie, dass die Menge der reellen Zahlen überabzählbar unendlich ist.

Lösung

Aufgabe 1

Aufgabe 2

Die Anzahl der Wörter aus einem Alphabet A mit einer bestimmten Länge l ist endlich. Die Zahl der Wörter, die mit der Länge l aus dem Alphabet A gebildet werden können, kann mit

\begin{array}{ccc} \text{Anzahl der Elemente des Alphabets}^\text{Wortl\"ange}&=&A^l \end{array}

berechen werden. Die Wortmenge A^\ast bildet sich nun aus den unendlich vielen Teilmengen A^i.

Um eine Abbildung der Wortmenge A^\ast auf die natürlichen Zahlen \mathbb{N} zu ermöglichen, ordnet man die einzelnen Wörter der Wortmenge nach der längenlexikografischen Ordnung.

Aufgabe 3

Bijektive Funktion

Aufgabenstellung

Verifzieren Sie, dass die folgende Funktion f : \mathbb{N}^+ \rightarrow \mathbb{Q}^+ eine bijektive Funktion ist und implementieren Sie eine Prozedur, die die zugehörige Umkehrfunktion f^{-1} berechnet.

f(n)=\begin{cases} 1, &\text{wenn }n=1;\\ f(\frac{n}{2}), & \text{wenn n gerade};\\ \frac{1}{f(n-1)}, & \text{wenn n ungerade}. \end{cases}

Lösung