BuK/IIm10/BuK-Übung05 G2

Wiki-Quelltext dieser Seite.

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

<language>Scheme</language>
== 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>
<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.
Das folgende Diagramm soll die Unregelmäßigkeit der Folge weiter verdeutlichen, indem die Anzahl der Glieder welche benötigt werden um bis zur <math>1</math> zu kommen benötigt werden dargestellt sind.

[[Bild:Simaklem_CollatzDiagr3.png]]


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.

== Aufgabe ==
Beweisen Sie, dass <math>{f}_{total}</math> nicht berechenbar ist, d.h. eine Prozedur <tt>totalmacher</tt> für <math>{f}_{total}</math>,
die eine partielle zahlentheoretische Funktion <math>{f}_{partiell}</math> nimmt, gibt es nicht.

== Lösung ==
Die Prozedur <tt>totalmacher</tt> soll prüfen ob eine Funktion total ist. Daher sollen "nicht anhatende Programme" auf ein Element "a" aus dem Wertebereich <math>{W}_{f}</math> abgebildet werden. Die Funktion wird so definiert:

<math>
{f}_{total}(x) = 
\left\lbrace
\begin{aligned}
   {f}_{partiell}(x)       & \text{, wenn } x \in {D}_{f}\\
   a & \text{, sonst}\\
\end{aligned}
</math>

;Satz
<math>{f}_{total}</math> ist nicht berechenbar.

;Beweis
Zuerst wird angenommen, dass <math>{f}_{total}</math> berechnenbar ist. 

<math>\rightarrow</math> Das Prädikat <math> x \in {D}_{f} </math> ist berechenbar.

<math>\rightarrow</math> Dann gibt es eine Prozedur <tt>hält_f_für_n?</tt>, welche das Prädikat berechnet.

Dies stellt ein Widerspruch zum Halteproblem dar, und daraus kann man schließen, das solch eine berechenbare Funktion <math>{f}_{total}</math>  nicht existiert.

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

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