BuK/IIm10/BuK-Übung05 G2

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
= Prozedur <tt>stoppt-collatz-bis?</tt> =

== Aufgabe ==
Schreiben Sie eine Scheme-Prozedur <tt>stoppt-collatz-bis?</tt>, die eine Zahl n als Eingabe erwartet und feststellt, ob die endlichen Collatzfolgen für <math> i = 2, 3, ..., n</math> existieren.

<language>Scheme</language>
== Lösung ==
Die Collatz-Folge, auch '''(3n+1)-Problem''' oder '''Ulam-Funktion''' genannt, ist so definiert:

<math>
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}
</math>

Die Vermutung ist, das die Folge, für eine beliebige Zahl <math>n \in \mathds{N}, n > 0</math> immer auf <math>1</math> endet.
Diese Vermutung konnte bisher noch nicht mathematisch bewiesen werden.

Wir können auch eine Prozedur angeben, welche die Folge berechnet:
<code id="4db830ef18b33">
(define collatz
  (lambda (n)
    (cond
      ((= n 1) 1)
      ((= (modulo n 2) 0) (collatz (/ n 2)))
      (else (collatz (+ 1 (* 3 n))))
)))
</code>
Dazu der Aufruf:
<run id="4db830ef18c1d">
(collatz 5)
</run>

Das Problem besteht darin, dass nicht festgestellt werden kann, ob die Folge auch für alle <math>n \in \mathds{N}</math> wirklich auf <math>1</math> endet.
Man könnte beweisen, das die Folge immer stoppt. Diese Prozedur sieht so aus:

<code id="4db830ef18b9f">
(define stoppt-collatz-bis?
  (lambda (start)
    (if (= 1 (collatz start))
    #t
    #f
)))
</code>

<run id="4db830ef18c88">
(stoppt-collatz-bis? 7)
</run>

Dieses Problem führt uns direkt zu dem Halteproblem: Es kann nicht festgestellt werden, ob diese/eine Prozedur stoppt.

= Beweis =
== Aufgabe ==
== Lösung ==

= Turingmaschine (TM) und RADOsche Funktion =
== Aufgabe ==
== Lösung ==

= Beweis =
== Aufgabe ==
== Lösung ==