BuK-Übung05 G2
Inhaltsverzeichnis |
Prozedur stoppt-collatz-bis?
Aufgabe
Schreiben Sie eine Scheme-Prozedur stoppt-collatz-bis?, die eine Zahl n als Eingabe erwartet und feststellt, ob die endlichen Collatzfolgen für i = 2, 3, ..., n existieren.
Lösung
Die Collatz-Folge, auch (3n+1)-Problem oder Ulam-Funktion genannt, ist so definiert:
collatz(n)= \left\lbrace \begin{aligned} 1 & \text{, wenn } n=1\\ collatz(n/2) & \text{, wenn } n \text{ gerade}\\ collatz(3n+1)& \text{, wenn } n \text{ ungerade}\\ \end{aligned}Die Vermutung ist, das die Folge, für eine beliebige Zahl n \in \mathds{N}, n > 0 immer auf 1 endet. Diese Vermutung konnte bisher noch nicht mathematisch bewiesen werden.
Wir können auch eine Prozedur angeben, welche die Folge berechnet:
Dazu der Aufruf:
Das Problem besteht darin, dass nicht festgestellt werden kann, ob die Folge auch für alle n \in \mathds{N} wirklich auf 1 endet. Das folgende Diagramm soll die Unregelmäßigkeit der Folge weiter verdeutlichen, indem die Anzahl der Glieder welche benötigt werden um bis zur 1 zu kommen benötigt werden dargestellt sind.
Man könnte beweisen, das die Folge immer stoppt. Diese Prozedur sieht so aus:
Dieses Problem führt uns direkt zu dem Halteproblem: Es kann nicht festgestellt werden, ob diese/eine Prozedur stoppt.
Aufgabe
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
Die Prozedur totalmacher soll prüfen ob eine Funktion total ist. Daher sollen "nicht anhatende Programme" auf ein Element "a" aus dem Wertebereich {W}_{f} abgebildet werden. Die Funktion wird so definiert:
{f}_{total}(x) = \left\lbrace \begin{aligned} {f}_{partiell}(x) & \text{, wenn } x \in {D}_{f}\\ a & \text{, sonst}\\ \end{aligned}- Satz
{f}_{total} ist nicht berechenbar.
- Beweis
Zuerst wird angenommen, dass {f}_{total} berechnenbar ist.
\rightarrow Das Prädikat x \in {D}_{f} ist berechenbar.
\rightarrow Dann gibt es eine Prozedur hält_f_für_n?, welche das Prädikat berechnet.
Dies stellt ein Widerspruch zum Halteproblem dar, und daraus kann man schließen, das solch eine berechenbare Funktion {f}_{total} nicht existiert.
Turingmaschine (TM) und RADOsche Funktion
Aufgabe
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
Fleißige Biber (engl. Busy Beaver) sind Turingmaschinen, die möglichst viele Einsen auf das Band schreiben, ohne in eine Endlosschleife zu geraten (d. h. die nach einer endlichen Anzahl Rechenschritte halten).
Formal kann eine Turingmaschine als 7-Tupel
M = (Q, \Sigma, \Gamma, \delta, q_0, \$, q_e)dargestellt werden:
- Q ist die endliche Zustandsmenge
- \Sigma ist das Eingabealphabet
- \Gamma ist das endliche Bandalphabet und es gilt \Sigma \subset \Gamma
- \delta: (Q \setminus \{q_f\})\times \Gamma \mapsto Q \times \Gamma \times \{ L, N, R \} ist die (partielle) Überführungsfunktion
- q_0 \in Q ist der Anfangszustand
- \$ \in \Gamma\setminus\Sigma ist das Bandvorbelegungszeichen
- q_e \in Q ist der akzeptierende Zustand
In AtoCC kann die Definition einer Turingmaschine direkt umgesetzt werden und anschaulich dargestellt werden. Für einen Übergang zwischen 2 Zuständen müssen folgende Dinge angegeben werden:
- Start- und Endzustand
- gelesenes Zeichen
- geschriebenes Zeichen
- Bewegung des Lesekopfes (Links, Keine(None) , Rechts)
Dieser Übergang anhand eines Pfeiles dargestellt. Folgend ein Beispiel für einen Busy Beaver für 2 Zusände.
Und einer für 3 Zustände:
Dieser Busy Beaver erzeugt folgende Konfiguration-Sequenz und es entstehen 6 Einsen auf dem Band.
