BuK-Übung05 G1
Inhaltsverzeichnis |
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
TM für n=1
Definition:
M = (\{q0, q1\}, \{1\}, \{0, 1\}, \delta, q0, 0, \{q1\})Übergange:
\begin{tabular}{l|c c } $\delta$ & $\texttt{0}$ & $\texttt{1}$ \\ \hline $q_{0}$& $(q_{1},\texttt{1},N)$ & - \\ $q_{1}$ & - & - \end{tabular}
TM für n=2
Definition:
M = (\{q0, q1, q2\}, \{1\}, \{0, 1\}, \delta, q0, 0, \{q2\})Übergänge:
\begin{tabular}{l|c c } $\delta$ & $\texttt{0}$ & $\texttt{1}$ \\ \hline $q_{0}$& $(q_{1},\texttt{1},R)$ & $(q_{1},\texttt{1},L)$ \\ $q_{1}$& $(q_{0},\texttt{1},L)$ & $(q_{2},\texttt{1},N)$ \\ $q_{2}$ & - & - \end{tabular}
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}