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_{t}
Die Funktion f_t ist definiert als:
f_t(x) = \begin{cases} f_p(x), & \mbox{wenn } x \in D_{f_p} \\ a, & \mbox{sonst, d.h. } x \in X \setminus D_{f_p} \end{cases}mit a \in Y und a \notin W_{f_p}. Dabei ist W_{f_p} \subseteq Y der Wertebereich von f_p.
"Kann man jede beliebige partielle Funktion f_p zu einer (zugehörigen) totalen f_t umkonstruieren? Genauer: Gibt es eine Prozedur f_{totalmacher}, die eine (partielle) Funktion f_p nimmt und die zugehörige totale f_t zurückgibt?"
Definition der totalen Funktion
Unter einer Abbildung f:X \rightarrow Y von der Menge X in die Menge Y verstehen wir eine Vorschrift, die jedem x \in X ein eindeutig bestimmtes y \in Y zuordnet. y bezeichnen wir mit f(x) und nennen es den Bildpunkt von x. Abbildungen werden auch Funktionen genannt. Die Menge X = D_f heißt Definitionsbereich von f.
Beweis
Die Funktion f_p ist nur ausführbar, ihr Definitionskontext ist dem gewünschten f_{totalmacher} also nicht bekannt. Somit benötigt der f_{totalmacher} das Prädikat haelt\_fuer\_n?, welches eine Prozedur nimmt und feststellt, ob (f\ n) für eine gegebene natürliche Zahl stoppt oder nicht.
In der BuK-Übung 01 wurde bereits gezeigt, daß eine wohldefinierte Funktion crazy existiert, welche eine Zahl akzeptiert und gleichzeitig nicht akzeptiert. Dieser Widerspruch zeigt, dass es keine Funktion haelt? geben kann. haelt? ist eine Spezialisierung der Funktion haelt\_fuer\_n? für den Fall n = 0. Da haelt\_fuer\_n? somit auch nicht berechenbar ist, ist folglich auch die gewünschte Funktion f_{totalmacher} nicht berechenbar.
Die Frage, ob f_{totalmacher} existiert, muss somit (leider leider) verneint werden. :-(
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}