Halteproblem

Aufgabe

Lösung

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

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

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

Für fie Funktion f(n) gibt es keine Umkehrfunktion, da diese nicht streng monoton ist.

Scheme Prozedur

Handrechnung

Effizienzsteigerung mit Memoizing