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

Beispiel-Aufruf für haelt:

Beispiel-Aufruf zu haelt-tricky:

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

Zum Beweis, dass die Menge der rationalen Zahlen abzählbar unendlich ist, muss der Nachweis der Existenz einer bijektiven Abbildung \mathbb{N} \rightarrow \mathbb{Q} erbracht werden. Dafür eignet sich das erste Cantor'sche Diagonalargument.

Ein weiterer Ansatz ist es, die Menge der rationalen Zahlen mit folgender Funktion zu beschreiben:

Lässt man dabei noch alle kürzbaren Brüche weg, so ergeben sich die Teilmengen:

Durch diese Vorgehensweise, können somit alle Elemente von \mathbb{Q}^+ ermittelt werden. Es kann festgestellt werden, dass das Ergebnis der Funktion f(n) für endliche n eine abzählbare endliche Menge ist. Das Ergebnis von f(\infty) ist demnach abzählbar unendlich und entspricht zudem \mathbb{Q}^+. Somit ist \mathbb{Q}^+ abzählbar unendlich. Das selbe muss demnach auch für \mathbb{Q}^- gelten, da beide Mengen die selbe Größe haben. Einzig die 0 muss noch abgebildet werden, was natürlich ebenfalls kein Problem darstellt.

Somit ist klar, dass eine bijektive Abbildung \mathbb{N} \rightarrow \mathbb{Q} existiert und somit \mathbb{Q} abzählbar unendlich ist.

Diese Funktion lässt sich ebenfalls in einem entsprechendem Algorithmus abbilden.

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.

Beispiel

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 nun die einzelnen Wörter der Wortmenge nach der längenlexikografischen Ordnung. Anschließend kann jedem Wort eine natürliche Zahl zugeordnet werden.

Beispiel

{| class="wikitable"

|- ! \epsilon!! a !! b !! c !! d !! aa |- | 1 || 2 || 3 || 4 || 5 || 6 |}

Aufgabe 3

Auflisten von allen reellen Zahlen zwischen 0 und 1:

Nimmt man nun die Ziffern auf der Diagonalen (a_{00},a_{11},...), ändert diese Zahlen nach dem Muster

\overline{a_i}=\begin{cases} a_{ii}+1, & \text{wenn }a_{ii}<9\\ 0, & \text{sonst} \end{cases}

und bildet aus den einzelnen Ziffern eine neue Zahl \overline{a}=0.\text{ }\overline{a_0}\text{ }\overline{a_1}\text{ }\overline{a_2}\text{ }\overline{a_3}..., so ist diese Zahl eine neue Zahl in \mathbb{R}. Dies kann unendlich oft wiederholt werden, man kann nie alle reelle Zahlen zwischen 0 und 1 auflisten. Damit ist auch eine Abbildung von den reellen Zahlen \mathbb{R} auf die natürlichen Zahlen \mathbb{N} nicht möglich.

Daraus folgt: \overline{Z} gilt nicht \rightarrow Z gilt.

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

Beispiel-Aufruf:

Beispiel-Aufruf mit Memoizing:

"Naive" Implementation der Umkehrfunktion

Beispielaufruf:

Implementation der echten Umkehrfunktion:

Beispielaufruf: