Halteproblem

Aufgabe

Spielen Sie die Betrachtungen zum Halteproblem 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 Berech- nung in einer gewissen Zeit T zu keinem Ergebnis führt. Verwenden Sie zeitbeschränkte Berechnungen, deren Implementierungsidee einige Kreativität erfordert.

Lösung für Racket

Die Lösungsidee besteht darin, einen neuen Thread für sie zu prüfende Prozedur zu starten. Der Hauptthread fragt anschließend periodisch ab, ob der andere Thread seine Berechnung beendet hat. Ist die Berechnung nach einer bestimmten Zeit nicht abgeschlossen, wird die Berechnung gestoppt und #f zurückgegegen. In der Praxis ist diese Lösungsvariante mit Threads und einem Timeout häufig anzutreffen.

Aufrufbeispiele:

Eine ähnliche Implementation in Java kann hier gefunden werden.

Beweise

Aufgabe 1

Zeigen Sie, dass die Menge der rationalen Zahlen abzählbar unendlich ist.

Lösung

Eine Menge ist dann abzählbar unendlich wenn sie gleichmächtig zur Menge der natürlichen Zahlen \mathbb{N} ist. Mit Cantors erstes Diagonalargument lässt sich zeigen, dass die unendliche Menge der rationalen Zahlen \mathbb{Q} gleichmächtig mit der Menge der natürlichen Zahlen \mathbb{N} ist.

Aufgabe 2

Zeigen Sie, dass die Wortmenge A^{\ast} über A abzählbar unendlich ist.

Lösung

Gegeben sei ein Alphabet A mit den Elementen \{a_1,a_2,a_3\ldots,a_n\} im weiteren Buchstaben genannt. Die Anzahl der Buchstaben ist n und endlich. Weiterhin sei die Ordnungsrelation a_1<a_2<a_3<\ldots<a_n für die Buchstaben gegeben.
Die Wortmenge A^{\ast} wird gebildet, in dem beliebige Buchstaben aus A verkettet werden. Die Länge eines Wortes wird über die Anzahl der Buchstaben festgelegt.
Beispiel: a_1 hat die Länge 1, a_1a_1a_3 hat die Länge 3 und als Spezialfall für das leere Wort \varepsilon mit der Länge 0.
Die Abbildung der Wörter aus A^{\ast} auf die natürlichen Zahlen \mathbb{N} wird wie folgt umgesetzt. Die Wörter werden ihrer Länge entsprechend angeordnet, wobei die kürzeren (Länge ist kleiner) zuerst verwendet werden. Wörter der selben Länge werden lexikographisch geordnet. Das erste Wort wird der 1 zugeordnet, das Zweite der 2 usw..
Angewendet ergibt sich:

Jedem Element der Wortmenge kann genau eine natürliche Zahl zugeornet werden. Die Wortmenge A^{\ast} über A ist also abzählbar unendlich.

Aufgabe 3

Zeigen Sie, dass die Menge der reellen Zahlen überabzählbar unendlich ist.

Lösung

Durch Widerspruch kann gezeigt werden, dass die Menge der reellen Zahlen \mathbb{R} überabzählbar unendlich ist. Für den Beweis wird das offene Intervall (0,1) betrachtet was eine echte Teilmenge der reellen Zahlen darstellt.
Annahme: Die Menge der reellen Zahlen im offenen Intervall (0,1) ist abzählbar.
Es muss eine bijektive Abbildung der reellen Zahlen auf die natürlichen Zahlen existieren. Sei nun l_{i} eine beliebige Folge von reellen Zahlen im offenen Intervall (0,1). Die Folge lässt sich dezimal wie folgt darstellen:

wobei l_{i} reelle Zahlen sind und a_{i;j} die Dezimalstellen dieser Zahlen. Nun lässt sich eine Zahl z konstruieren die nicht in der Folge l_{i} zu finden ist.
z = 0,f_1f_2f_3\cdots
wobei f_i=\begin{cases} 0, &\text{wenn } a_{i;i} = 9;\\ a_{i;i} + 1 &\text{wenn } a_{i;i} < 9;\\ \end{cases}
Diese Diagonalzahl z unterscheidet sich von allen anderen Zahlen der Folge l_{i} und ist ebenfalls im Intervall (0,1). Es kann also für jede beliebige Folge l_{i} eine Zahl gefunden werden die nicht in der Folge enthalten ist.
Es existiert keine surjektive Abbildung der natürlichen Zahlen auf das offene Intervall (0,1). D.h. es kann auch keine bijektive Abbildung existieren. Die Menge der reellen Zahlen im Intervall (0,1) ist also nicht abzählbar. Sie ist überabzählbar unendlich. Da das Intervall eine echte Teilmenge der reellen Zahlen \mathbb{R} ist, gilt das auch für die Menge der reellen Zahlen.

Kreativität

Schauen Sie sich das Video an, um den Begriff der Kreativität besser zu verstehen.

Bijektive Funktion

Aufgabe

Verifizieren 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.

Lösung

Scheme Prozedur

Handrechnung

Beweis

Es existiert eine Funktion f^{-1}:\mathbb{Q}^+ \rightarrow \mathbb{N}^+, die die Umkehrfunktion von f darstellt. Dann muss gelten:
(1): f^{-1}(f(n)) = n \ ;\forall n \in \mathbb{N}^+
D.h. aber auch, dass alle Zahlen aus \mathbb{N}^+ auf genau eine Zahl aus \mathbb{Q}^+ abgebildet werden. Die Abbildung durch die Funktion f ist injektiv. Würde das nicht gelten wäre die Gleichung (1) nicht erfüllt.
Die Abbildung der Funktionswerte von \mathbb{Q}^+ auf \mathbb{N}^+ ist ebenfalls injektiv. Das reicht aber noch nicht um die Bijektivität der Funktion f zu beweisen. Dazu muss gelten:
(2): f(f^{-1}(x)) = x \ ;\forall x \in \mathbb{Q}^+
Aus Gleichung (2) ist zu entnehmen, dass wirklich alle Werte (nicht nur die Funktionswerte aus f) aus \mathbb{Q}^+ auf \mathbb{N}^+ abgebildet werden.
Gegeben ist die Umkehrfunktion:
f^{-1}(x)=\begin{cases} 1, &\text{wenn }x = 1;\\ 2*f^{-1}(x - 1) , & \text{wenn } x > 1;\\ f^{-1}(\frac{1}{x}) + 1 , & \text{sonst}; \end{cases}
Beweis Gleichung (1)
n = 1 : trivial
n gerade :
\begin{array}{ccl} f^{-1}(f(n)) = n & | & n = 2m \\ f^{-1}(f(2m)) = 2m & | & f(2m) \rightarrow f(\frac{2m}{2}) + 1 \rightarrow f(m) + 1\\ f^{-1}(f(m) + 1) = 2m & | & f(m) + 1 > 1 \text{ ,da } f(m) \in \mathbb{Q}^+\\ 2 * f^{-1}(f(m) + 1 - 1) = 2m & | & \text{teile durch 2}\\ f^{-1}(f(m)) = m & \\ \end{array}
n ungerade :
\begin{array}{ccl} f^{-1}(f(n)) = n & | & n = 2m + 1 \\ f^{-1}(f(2m + 1)) = 2m + 1 & | & f(2m + 1) \rightarrow \frac{1}{f(2m + 1 - 1)} \rightarrow \frac{1}{f(2m)}\\ f^{-1}(\frac{1}{f(2m)}) = 2m + 1 & | & f(2m) \rightarrow f(\frac{2m}{2}) + 1 \rightarrow f(m) + 1\\ f^{-1}(\frac{1}{f(m) + 1}) = 2m + 1 & | & f(m) + 1 > 1 \rightarrow \frac{1}{f(m) + 1} < 1\\ f^{-1}(f(m) + 1) + 1 = 2m + 1 & | & f(m) + 1 > 1 \\ 2 * f^{-1}(f(m)) + 1 = 2m + 1 & | & -1 ; /2\\ f^{-1}(f(m)) = m \end{array}
Damit ist für alle n \in \mathbb{N}^+ gezeigt, das die Gleichung erfüllt ist.
Beweis Gleichung (2)
x = 1 : trivial
x > 1 :
\begin{array}{ccl} f(f^{-1}(x)) = x & | & x > 1 \\ f(2*f^{-1}(x - 1)) = x & | & n = f^{-1}(x - 1) \\ f(2*n) = x & | & f(2n) \rightarrow f(\frac{2n}{2}) + 1\\ f(n) + 1 = x & | & -1; n = f^{-1}(x - 1)\\ f(f^{-1}(x - 1)) = x - 1 & | & y = x - 1\\ f(f^{-1}(y)) = y \end{array}
x < 1 :
\begin{array}{ccl} f(f^{-1}(x)) = x & | & x < 1 \\ f(f^{-1}(\frac{1}{x}) + 1) = x & | & y = \frac{1}{x} > 1\\ f(2*f^{-1}(y - 1) + 1) = \frac{1}{y} & | & 2*f^{-1}(y - 1) + 1 = 2*n + 1 \rightarrow \text{ ungerade, mit } n = f^{-1}(y - 1)\\ \frac{1}{f(2*f^{-1}(y - 1) + 1 - 1)} = \frac{1}{y} & | & \text{reziprok bilden}\\ f(2*f^{-1}(y - 1)) = y & | & 2*f^{-1}(y - 1) \rightarrow \text{ gerade}\\ f(f^{-1}(y - 1)) + 1 = y & | & -1; z = y - 1\\ f(f^{-1}(z)) = z \end{array}
Für alle x \in \mathbb{Q}^+ ist somit gezeigt, dass die Gleichung (2) erfüllt ist.
Da jetzt bewiesen ist, dass die Gleichung (1) und (2) mit der gegebenen Umkehrfunktion f^{-1} gelten handelt es sich bei der Funktion f um eine bijektive Funktion. Jeder Zahl aus \mathbb{N}^+ kann genau eine Zahl aus \mathbb{Q}^+ zugeordnet werden und umgekehrt.

Prozedur für die Umkehrfunkion

Die folgende Funktion berechnet die Umkehrfunktion für gültige Eingaben in C#. Die Klasse Fraction stellt die rationale Zahlen dar.

Func<Fraction, int> reverse = null;
reverse = x => 
  (x == Fraction.One) ? 1 : 
    (x > Fraction.One) ? reverse (x - 1) * 2 : reverse (Fraction.Inverse (x)) + 1;