BuK/IIm10/BuK-Übung05 G1

Wiki-Quelltext dieser Seite.

= Prozedur ''stoppt-collatz-bis?'' =

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

<language>Scheme</language>
== Lösung ==
<code id="4daeb433e6a03">
(define collatz
  (lambda (n)
    (cond
      ((= 1 n) (list 1))
      ((= (modulo n 2) 0) (cons n (collatz (/ n 2))))
      (else
       (cons n (collatz(+ (* 3 n) 1)))))))

(define stoppt-collatz-bis?
  (lambda (n)
    (cond
      ((= n 1) #t)
      (else
       (collatz n) (stoppt-collatz-bis? (- n 1))))))
</code>

<run id="4daeb433e6a75">(collatz 7)</run>

<run id="4daeb433e6ada">(stoppt-collatz-bis? 10)</run>

= Beweis =

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

== Lösung ==
=== Definition von <math>f_{t}</math> ===
Die Funktion <math>f_t</math> ist definiert als:

<math>f_t(x) = 
\begin{cases} 
f_p(x), & \mbox{wenn } x \in D_{f_p} \\ 
a, & \mbox{sonst, d.h. } x \in X \setminus D_{f_p} 
\end{cases}
</math>

mit <math>a \in Y</math> und <math>a \notin W_{f_p}</math>. Dabei ist <math>W_{f_p} \subseteq Y</math> der Wertebereich von <math>f_p</math>.

"Kann man jede beliebige partielle Funktion <math>f_p</math> zu einer (zugehörigen) totalen <math>f_t</math> umkonstruieren? Genauer: Gibt es eine Prozedur <math>f_{totalmacher}</math>, die eine (partielle) Funktion <math>f_p</math> nimmt und die zugehörige totale <math>f_t</math> zurückgibt?"

=== Definition der totalen Funktion ===

Unter einer Abbildung <math>f:X \rightarrow Y</math> von der Menge <math>X</math> in die Menge <math>Y</math> verstehen wir eine Vorschrift, die jedem <math>x \in X</math> ein eindeutig bestimmtes <math>y \in Y</math> zuordnet. <math>y</math> bezeichnen wir mit <math>f(x)</math> und nennen es den Bildpunkt von <math>x</math>. Abbildungen werden auch Funktionen genannt. Die Menge <math>X = D_f</math> heißt Definitionsbereich von <math>f</math>.

=== Beweis ===

Die Funktion <math>f_p</math> ist nur ausführbar, ihr Definitionskontext ist dem gewünschten <math>f_{totalmacher}</math> also nicht bekannt. Somit benötigt der <math>f_{totalmacher}</math> das Prädikat <math>haelt\_fuer\_n?</math>, welches eine Prozedur nimmt und feststellt, ob <math>(f\ n)</math> für eine gegebene natürliche Zahl stoppt oder nicht.

In der [[BuK-Übung_01|BuK-Übung 01]] wurde bereits gezeigt, daß eine wohldefinierte Funktion <math>crazy</math> existiert, welche eine Zahl akzeptiert und gleichzeitig nicht akzeptiert. Dieser Widerspruch zeigt, dass es keine Funktion <math>haelt?</math> geben kann. <math>haelt?</math> ist eine Spezialisierung der Funktion <math>haelt\_fuer\_n?</math> für den Fall <math>n = 0</math>. Da <math>haelt\_fuer\_n?</math> somit auch nicht berechenbar ist, ist folglich auch die gewünschte Funktion <math>f_{totalmacher}</math> nicht berechenbar.

Die Frage, ob <math>f_{totalmacher}</math> existiert, muss somit (leider leider) verneint werden. :-(

= Turingmaschine (TM) und RADOsche Funktion =

== Aufgabenstellung ==
Machen Sie sich mit dem in AtoCC eingebauten TM-Modell vertraut. Tragen Sie einige TM zusammen, die das Busy-Beaver-Problem für kleinere n lösen. Verwenden Sie AtoCC, um diese zu simulieren.

== Lösung ==
=== TM für n=1 ===
'''Definition:'''
<math>M = (\{q0, q1\}, \{1\}, \{0, 1\}, \delta, q0, 0, \{q1\})</math>

'''Übergange:'''
<math>\begin{tabular}{l|c c }
$\delta$ & $\texttt{0}$ & $\texttt{1}$ \\
\hline
$q_{0}$& $(q_{1},\texttt{1},N)$  & -  \\
$q_{1}$ & -  & -  
\end{tabular}</math>

[[Datei:Busy Beaver1.png]]

=== TM für n=2 ===
'''Definition:'''
<math>M = (\{q0, q1, q2\}, \{1\}, \{0, 1\}, \delta, q0, 0, \{q2\})</math>

'''Übergänge:'''
<math>\begin{tabular}{l|c c }
$\delta$ & $\texttt{0}$ & $\texttt{1}$ \\
\hline
$q_{0}$& $(q_{1},\texttt{1},R)$ & $(q_{1},\texttt{1},L)$  \\
$q_{1}$& $(q_{0},\texttt{1},L)$ & $(q_{2},\texttt{1},N)$  \\
$q_{2}$ & -  & -  
\end{tabular}
</math>

[[Datei:Busy Beaver2.png]]

= Beweis =

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

<language>Scheme</language>
<language>Scheme</language>
<language>Scheme</language>
== Lösung ==
In der Zeichung ist zu erkennen, dass es für eine natürliche Zahl <math>n</math> durch Anwendung der Aufzählfunktionen <math>f_1</math> und <math>f_2</math> zwei Abbildungen gibt. Eine Abbildung in<math> M_1</math> und ein in <math>M_2</math>.

[[Datei:Aufgabe4.png]]

Um nachzuweisen, dass <math>M_1 \cup M_2</math> ebenfalls aufzählbar ist, benötigt man eine Funktion <math>g</math>, die diese Menge aufzählt. Die Ausgaben dieser Funktion wären folgende:

:<math>
\begin{array}{ccc}
g(0) & = & f_1(0) \\
g(1) & = & f_2(0) \\
g(2) & = & f_1(1) \\
g(3) & = & f_2(1) \\
g(4) & = & f_1(2) \\
g(5) & = & f_2(2) \\
\end{array}
</math>

Es ist zu erkennen, dass die Funktion <math>g</math> wie folgend definiert sein muss.

:<math>
g(n)=\begin{cases}
f_1(\frac{n}{2}) & \text{,wenn } n \text{ gerade} \\
f_2(\frac{n-1}{2}) & \text{, sonst (wenn } n \text{ ungerade)}
\end{cases}
</math>

<code id="4daec2e09d64c" hidden>
;;; STREAMS - Implementation mit verzoegerter Evaluation (delay, force)
;;  als cons aus einem Kopfglied und einem verzögerten Reststream
  
  ;; Selektoren
  
  (define stream-car car)
  
  (define stream-cdr
    (lambda (stm)
      (force (cdr stm))))
  
  ;; Konstruktoren
  
  (define-syntax stream-cons
    (syntax-rules ()
      ((_ head tail) (cons head (delay tail)))))
  
  ;; Praedikat
  
  (define stream?
    (lambda (stm)
      (and (pair? stm)(promise? (cdr stm)))))
  
  ;; Operationen mit streams
  
  (define make-stream 
    (lambda (seed proc)
      (letrec 
          ((stream-builder
            (lambda (n)
              (stream-cons n (stream-builder (proc n))))))
        (stream-builder seed))))
  
  (define *the-end-of-stream-tag*
    (make-stream
     "eos"
     (lambda (str) str)))
  
  (define stream-item
    (lambda (str k)
      (if (= k 0)
          (stream-car str)
          (stream-item (stream-cdr str) (- k 1)))))
  
  (define stream->list
    (lambda (str n)
      (if (<= n 0)
          '()
          (cons 
           (stream-car str) 
           (stream->list (stream-cdr str) (- n 1))))))
  
  (define stream-map
    (lambda (f str)
      (stream-cons
       (f (stream-car str))
       (stream-map f (stream-cdr str)))))
  
  (define print-stream
  (lambda (stm n)
    (cond
     ((<= n 0) (display "...\n"))
     (else
      (display (stream-car stm))
      (display ", ")
      (print-stream (stream-cdr stm) (- n 1))))))
  
  (define stream+
    (lambda (stm1 stm2)
      (stream-cons
       (+ (stream-car stm1) (stream-car stm2))
       (stream+ (stream-cdr stm1) (stream-cdr stm2)))))

;---------------------------------------------------------

(define nat-stream
  (lambda (start)
    (stream-cons start (nat-stream (+ start 1)))))

(define natzahlen (nat-stream 0))
</code>

<code id="4daec2e09d6b8">
(define f1
  (lambda (n)
    (* n 2)))

(define f2
  (lambda (n)
    (+ (* 2 n) 1)))

(define g
  (lambda (n)
    (cond
      ((= (modulo n 2) 0) (f1 (/ n 2)))
      (else
       (f2 (/ (- n 1) 2))))))

(define gstream (stream-map g natzahlen))
</code>

<run id="4daec2e09d736">(print-stream gstream 20)</run>