BuK/IIm10/BuK-Übung02 G1

Wiki-Quelltext dieser Seite.

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

Hinweis: Definieren Sie ggf. auch eine Prozedur <math>haelt-tricky?</math>, die <math>\#t</math> zurück gibt, wenn das betrachtete Programm P ein Ergebnis berechnet, und <math>\#f</math>, 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==
# Zeigen Sie, dass die Menge der rationalen Zahlen abzählbar unendlich ist.
# Zeigen Sie, dass die Wortmenge <math>A^\ast</math> über <math>A</math> abzählbar unendlich ist.
# Zeigen Sie, dass die Menge der reellen Zahlen überabzählbar unendlich ist.

==Lösung==

=Bijektive Funktion=
==Aufgabenstellung==
Verifzieren Sie, dass die folgende Funktion <math>f : \mathbb{N}^+ \rightarrow \mathbb{Q}^+</math> eine bijektive Funktion ist und  implementieren Sie eine Prozedur, die die zugehörige Umkehrfunktion <math>f^{-1}</math> berechnet.
:<math>
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}
</math>

==Lösung==