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.