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
Definition von f_{total}
Die Funktion f_{total} ist definiert als:
f_{total}(x) = \begin{cases} f_{partiell}(x), & \mbox{wenn } x \in D_{f_{partiell}} \\ a, & \mbox{sonst, d.h. } x \in X \setminus D_{f_{partiell}} \end{cases}mit a \in Y und a \notin W_{f_{partiell}}. Dabei ist W_{f_{partiell}} \subseteq Y der Wertebereich von f_{partiell}.
Beweis
Der Beweis erfolgt durch den indirekten Beweis. Dafür wird die Annahme getroffen, dass f_{total} berechnbar ist. Dann ist das Prädikat x \in D_f? berechenbar. Somit ist haelt_fuer_n? ebenfalls berechenbar. Dies widerspricht jedoch dem HALTEPROBLEM. Damit ist die Annahme falsch, also f_{total} nicht berechenbar.
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
In diesem Wikipedia Artikel ist eine Erläuterung des Busy-Beaver zu finden.
Obwohl die Turing-Maschine ein Produkt der Theoretischen Informatik ist, ist in diesem Video zu sehen, dass dieses Modell nur theoretische Spielerei ist. In dem Video ist eine TM zu sehen, die den Busy Beaver mit 4 Zuständen berechnet.
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}