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. 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.