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.

= Beweis =

== 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 ==
Machen Sie sich mit dem in AtoCC eingebauten TM-Modell vertraut. Tragen Sie einige TM zusammen, die das Busy-Beaver-Problem für kleinere <math>n</math> 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). Die '''RADO-Funktion''' gibt die maximale Anzahl der Einsen an, die ein fleißiger Biber mit einer gegebenen Anzahl von Zuständen schreiben kann. 

Formal kann eine Turingmaschine als 7-Tupel 
<math> M = (Q, \Sigma, \Gamma, \delta, q_0, \$, q_e) </math> 
dargestellt werden:

* <math>Q</math> ist die endliche Zustandsmenge
* <math>\Sigma</math> ist das Eingabealphabet
* <math>\Gamma</math> ist das endliche Bandalphabet und es gilt <math>\Sigma \subset \Gamma</math>
* <math>\delta: (Q \setminus \{q_f\})\times \Gamma \mapsto Q \times \Gamma \times \{ L, N, R \}</math> ist die (partielle) Überführungsfunktion
* <math>q_0 \in Q</math> ist der Anfangszustand
* <math>\$ \in \Gamma\setminus\Sigma</math> ist das Bandvorbelegungszeichen
* <math>q_e \in Q</math> ist der akzeptierende Zustand

In [http://www.atocc.de/ 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)

Ein Übergang wird anhand eines Pfeiles dargestellt. Folgend ein Beispiel für einen Busy Beaver mit 2 Zusänden.

[[Bild:Simaklem_Tm_bb_2z.png|center|500px]]

Und einer für 3 Zustände:
[[Bild:Busy_beaver_3states.png‎|center|300px|Busy Beaver mit 3 Zuständen]]

Dieser Busy Beaver erzeugt folgende Konfiguration-Sequenz und es entstehen 6 Einsen auf dem Band.

[[Bild:Simaklem_Tm_bb_3z_configuration.png|center|500px]]

= Beweis =

== Aufgabe ==

Zeigen Sie, dass die Vereinigungsmenge <math>M_1\cup{}M_2</math> zweier aufzählbarer Mengen <math>M_1\subseteq{}A^{\ast}</math>
und <math>M_2\subseteq{}A^{\ast}</math> wiederum eine aufzählbare Menge ist.

== Lösung ==

Wenn die Mengen <math>M_1</math> und <math>M_2</math> aufzählbar sind, so gibt es zwei Funktionen <math>f_1:\mathbb{N}\rightarrow{}M_1</math> und <math>f_2:\mathbb{N}\rightarrow{}M_2</math>, die diese Mengen aufzählen.<br>
'''Zu Zeigen:''' Es existiert eine Funktion <math>g:\mathbb{N}\rightarrow{}M_1\cup{}M_2</math>, die die Vereinigungsmenge aufzählt.<br>
Mit Hilfe der Funktionen <math>f_1</math> und <math>f_2</math> können zwar die Mengen aufgezählt werden, jedoch muss sichergestellt sein, dass alle natürlichen Zahlen für jeweils <math>f_1</math> und <math>f_2</math> verwendet werden. Dazu findet eine Aufteilung der natürlichen Zahlen statt. Die Geraden werden für die Funktion <math>f_1</math> und die Ungeraden für die Funktion <math>f_2</math> benutzt. Diese Aufteilung verlangt aber auch, dass das Funktionsargument der Funktionen  <math>f_1</math> und <math>f_2</math> wieder auf alle natürlichen Zahlen abgebildet wird.<br>
Die folgende Funktion zählt die Vereinigungsmenge <math>M_1\cup{}M_2</math> auf.<br>
<math>
g(n)=
\begin{cases}
f_1(\frac{n}{2}), & \text{wenn }n\text{ gerade}\\
f_2(\frac{n-1}{2}), & \text{wenn }n\text{ ungerade}
\end{cases}
</math>

In Scheme kann die Vereinigungmenge sehr elegant folgendermaßen aufgezählt werden:
<code>
(define stream-zip
  (λ (stm1 stm2)
    (stream-cons (stream-car stm1) (stream-zip stm2 (stream-cdr stm1)))))
</code>

Diese Prozedur arbeitet wie ein Reißverschluss. Es werden "automatisch" abwechseln Elemente aus den beiden Mengen in den Ergebnis-Stream übernommen. Dazu wird das erste Element des ersten Streams (stm1) verwendet und an dieses mit einem rekursiven Aufruf der Rest-Stream angehängt. Beim rekursiven Aufruf werden nun aber die Parameter stm1 und stm2 vertauscht.

Zur Veranschaulichung erzeugen wir uns die Menge der natürlichen Zahlen und die Menge der Quadratzahlen.
<code>
(define f1
  (λ (n)
    n))

(define f2
  (λ (n)
    (* n n)))

(define m1 (stream-map f1 natzahlen))
(define m2 (stream-map f2 natzahlen))
</code>

Die Aufzählfunktion für die Vereinigungsmenge sieht nun folgendermaßen aus:
<code>
(define g
  (λ (n)
    (stream-item (stream-zip m1 m2) n))) 
</code>

<run>
(g 5)
</run>

Nutzt man diese Aufzählfunktion nun, um einen Stream für die Vereinigungsmenge zu erzeugen, so kann man an der Ausgabe gut erkennen, dass abwechseln Elemente der Ausgangsmengen erzeugt werden.
<code>
(define r (stream-map g natzahlen))
</code>

<run>
(print-stream r 20)
</run>