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 LaTeX: f_{t}

Die Funktion LaTeX: f_t ist definiert als:

LaTeX: 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 LaTeX: a \in Y und LaTeX: a \notin W_{f_p}. Dabei ist LaTeX: W_{f_p} \subseteq Y der Wertebereich von LaTeX: f_p.

Die Frage, frei nach (nicht für die Allgemeinheit sichtbarem) Skript von Prof.Dr. Christian Wagenknecht:

"Kann man jede beliebige partielle Funktion LaTeX: f_p zu einer (zugehörigen) totalen LaTeX: f_t umkonstruieren? Genauer: Gibt es eine Prozedur LaTeX: f_{totalmacher}, die eine (partielle) Funktion LaTeX: f_p nimmt und die zugehörige totale LaTeX: f_t zurückgibt?" [Bearbeiten] Definition der totalen Funktion

Unter einer Abbildung LaTeX: f:X \rightarrow Y von der Menge LaTeX: X in die Menge LaTeX: Y verstehen wir eine Vorschrift, die jedem LaTeX: x \in X ein eindeutig bestimmtes LaTeX: y \in Y zuordnet. LaTeX: y bezeichnen wir mit LaTeX: f(x) und nennen es den Bildpunkt von LaTeX: x. Abbildungen werden auch Funktionen genannt. Die Menge LaTeX: X = D_f heißt Definitionsbereich von LaTeX: f. [Bearbeiten] Beweis

Die Funktion LaTeX: f_p ist nur ausführbar, ihr Definitionskontext ist dem gewünschten LaTeX: f_{totalmacher} also nicht bekannt. Somit benötigt der LaTeX: f_{totalmacher} das Prädikat LaTeX: haelt\_fuer\_n?, welches eine Prozedur nimmt und feststellt, ob LaTeX: (f\ n) für eine gegebene natürliche Zahl stoppt oder nicht.

In der BuK-Übung 01 wurde bereits gezeigt, daß eine wohldefinierte Funktion LaTeX: crazy existiert, welche eine Zahl akzeptiert und gleichzeitig nicht akzeptiert. Dieser Widerspruch zeigt, dass es keine Funktion LaTeX: haelt? geben kann. LaTeX: haelt? ist eine Spezialisierung der Funktion LaTeX: haelt\_fuer\_n? für den Fall LaTeX: n = 0. Da LaTeX: haelt\_fuer\_n? somit auch nicht berechenbar ist, ist folglich auch die gewünschte Funktion LaTeX: f_{totalmacher} nicht berechenbar.

Die Frage, ob LaTeX: 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:

Übergange:

TM für n=2

Definition:

Übergänge:

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}