Prozedur stoppt-collatz-bis?

Aufgabenstellung

Schreiben Sie eine Scheme-Prozedur stoppt-collatz-bis?, die eine Zahl n als Eingabe erwartet und feststellt, ob die endlichen Collatzfolgen für i=\text{ }2,3,...,n existieren.

Lösung

Beweis

Aufgabenstellung

Beweisen Sie, dass f_{total} nicht berechenbar ist, d.h. eine Prozedur totalmacher für f_{total} , die eine partielle zahlentheoretische Funktion f_{partiell} nimmt, gibt es nicht.

Lösung

Turingmaschine (TM) und RADOsche Funktion

Aufgabenstellung

Machen Sie sich mit dem in AtoCC eingebauten TM-Modell vertraut. Tragen Sie einige TM zusammen, die das Busy-Beaver-Problem für kleinere n lösen. Verwenden Sie AtoCC, um diese zu simulieren.

Lösung

Beweis

Aufgabenstellung

Zeigen Sie, dass die Vereinigungsmenge M_1 \cup M_2 zweier aufzählbarer Mengen M_1 \subseteq A^* und M_2 \subseteq A^* wiederum eine aufzählbare Menge ist.

Lösung

In der Zeichung ist zu erkennen, dass es für eine natürliche Zahl n durch Anwendung der Aufzählfunktionen f_1 und f_2 zwei Abbildungen gibt. Eine Abbildung in M_1 und ein in M_2.

Um nachzuweisen, dass M_1 \cup M_2 ebenfalls aufzählbar ist, benötigt man eine Funktion g, die diese Menge aufzählt. Die Ausgaben dieser Funktion wären folgende:

\begin{array}{ccc} g(0) & = & f_1(0) \\ g(1) & = & f_2(0) \\ g(2) & = & f_1(1) \\ g(3) & = & f_2(1) \\ g(4) & = & f_1(2) \\ g(5) & = & f_2(2) \\ \end{array}

Es ist zu erkennen, dass die Funktion g wie folgend definiert sein muss.

g(n)=\begin{cases} f_1(\frac{n}{2}) & \text{,wenn } n \text{ gerade} \\ f_2(\frac{n-1}{2}) & \text{, sonst (wenn } n \text{ ungerade)} \end{cases}