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}
Zusatz: Aufzählfunktion der Schnittmenge
Etwas schwieriger wird es, wenn wir beweisen sollen, dass wenn M1 und M2 aufzählbar sind, auch die Schnittmenge von M1 und M2 aufzählbar ist. Dazu muss ebenfalls eine surjektive und berechenbare Funktion g existieren, die unter Verwendung von f1 und f2 die Schnittmenge von M1 und M2 aufzählt.
Hierbei existiert das Problem, dass wir nicht einfach prüfen können, ob ein Element aus M1 auch in M2 enthalten ist. Da dazu alle Elemente untersucht werden müssen, würde die Funktion nicht zum Ende kommen, bevor alle Elemente aufgezählt wurden. Also müssen wir uns wieder der zeitbeschränkten Evaluation bedienen und der Prüfung, ob ein Element in einer der Mengen enthalten ist, nur eine bestimmte Zeit zur Verfügung stellen.
Wir können aber noch einen weiteren Trick verwenden. Indem wir einfach Listen L1 und L2 für die ersten n Elemente jeder Menge erstellen und prüfen, ob f1(n) in L2 oder f2(n) in L1 enthalten ist. Wenn ja, dann wird das entsprechende n-te Element von M1, bzw. M2 zurückgegeben, ansonsten irgendein beliebeiges a, welches in der Schnittmenge von M1 und M2 sicher enthalten ist. Um dieses a zu finden, können wir einfach die Funktion zunächst mit n=0 aufrufen und dann das n solange zu inkrementieren, bis f1(n) in L2 oder f2(n) in L1 enthalten ist und das erste so gefundene Element zurückgeben.
Das führt uns zur folgenden Implementierung:
Zur Aufzählung verwenden wir auch hier wieder Streams und erwarten natürlich nur ungeraden Quadratzahlen: