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_{total}</math> ===
Die Funktion <math>f_{total}</math> ist definiert als:

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

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

=== Beweis ===

Der Beweis erfolgt durch den indirekten Beweis. Dafür wird die Annahme getroffen, dass <math>f_{total}</math> berechnbar ist.
Dann ist das Prädikat <math>x \in D_f?</math> berechenbar.
Somit ist haelt_fuer_n? ebenfalls berechenbar.
Dies widerspricht jedoch dem HALTEPROBLEM. Damit ist die Annahme falsch, also <math>f_{total}</math> nicht berechenbar.

= 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 ==
[http://de.wikipedia.org/wiki/Busy_Beaver In diesem Wikipedia Artikel] ist eine Erläuterung des Busy-Beaver zu finden. 

Obwohl die Turing-Maschine ein Produkt der Theoretischen Informatik ist, ist [http://www.youtube.com/watch?v=2PjU6DJyBpw&feature=player_detailpage in diesem Video] zu sehen, dass dieses Modell nur theoretische Spielerei ist. In dem Video ist eine TM zu sehen, die den Busy Beaver mit 4 Zuständen berechnet.
=== 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]]

<language>Scheme</language>
= 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.




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

== Zusatz: Aufzählfunktion der Schnittmenge ==

Etwas schwieriger wird es, wenn wir beweisen sollen, dass wenn M1 und M2 aufzählbar sind, auch die Schnittmenge von M1 und M2 aufzählbar ist.
Dazu muss ebenfalls eine surjektive und berechenbare Funktion g existieren, die unter Verwendung von f1 und f2 die Schnittmenge von M1 und M2 aufzählt.

[[Datei:Aufgabe4 2.png]]

Hierbei existiert das Problem, dass wir nicht einfach prüfen können, ob ein Element aus M1 auch in M2 enthalten ist. Da dazu alle Elemente untersucht werden müssen, würde die Funktion nicht zum Ende kommen, bevor alle Elemente aufgezählt wurden.
Also müssen wir uns wieder der zeitbeschränkten Evaluation bedienen und der Prüfung, ob ein Element in einer der Mengen enthalten ist, nur eine bestimmte Zeit zur Verfügung stellen.

Wir können aber noch einen weiteren Trick verwenden. Indem wir einfach Listen L1 und L2 für die ersten n Elemente jeder Menge erstellen und prüfen, ob f1(n) in L2 oder f2(n) in L1 enthalten ist. Wenn ja, dann wird das entsprechende n-te Element von M1, bzw. M2 zurückgegeben, ansonsten irgendein beliebeiges a, welches in der Schnittmenge von M1 und M2 sicher enthalten ist.
Um dieses a zu finden, können wir einfach die Funktion zunächst mit n=0 aufrufen und dann das n solange zu inkrementieren, bis f1(n) in L2 oder f2(n) in L1 enthalten ist und das erste so gefundene Element zurückgeben.

Das führt uns zur folgenden Implementierung:

<code id="4dbfcdea47da9">
;Prüft ob ein Element in einer Liste enthalten ist
(define n-in-l
  (lambda (n l)
    (if (null? l)
        #f
        (if (= n (car l))
          #t
          (n-in-l n (cdr l))))))
;Aufzählfunktion für die Menge M1 (Menge der Quadratzahlen)
(define f1
  (lambda (n)
    (* n n)))
;Aufzählfunktion für die Menge M2 (Menge der ungeraden Zahlen)
(define f2
  (lambda (n)
    (+ (* 2 n) 1)))
;Liefert alle Elemente der Menge M, die durch die Funktion f aufgezählt wird von f(0) bis f(n)
(define get-l
  (lambda (n f)
    (if (= 0 n)
        (list (f 0))
        (append (list (f n)) (get-l (- n 1) f)))))
;Aufzählfunktion für die Schnittmenge von M1 und M2
(define g
  (lambda (n)
    (let ((l1 (get-l n f1)) (l2 (get-l n f2)))
        (if (n-in-l (f1 n) l2)
            (f1 n)
            (if (n-in-l (f2 n) l1)
                (f2 n)
                first-elem)))));a
;Liefert das erste gemeinsame Element der Mengen M1 und M2 ab einer bestimmten natürlichen Zahl n welches für die Aufzählfunktion verwendet wird
(define first-elem-from
  (lambda (n)
    (let ((l1 (get-l n f1)) (l2 (get-l n f2)))
        (if (n-in-l (f1 n) l2)
            (f1 n)
            (if (n-in-l (f2 n) l1)
                (f2 n)
                (first-elem-from (+ n 1)))))))
;Liefert das erste gemeinsame Element der Mengen M1 und M2
(define first-elem
  (first-elem-from 0))
</code>
<code id="4dbfcdea47e33" hidden>
;Funktionen für die Arbeit mit Streams

;Liefert das erste Element eines Streams
(define head car)

;Liefert den Rest-Stream ohne dem ersten Element
(define (tail stream) (force (cdr stream)))

;Fügt ein Element einem Stream hinzu
(define-syntax cons-stream
  (syntax-rules ()
    ((cons-stream x y)
     (cons x (delay y)))))

(define (g-starting-from n)
 (cons-stream (g n) 
  (g-starting-from (+ n 1))))

;Stream für alle Elemente der Schnittmenge von M1 und M2
(define g-stream
  (g-starting-from 0))

;Liefert die ersten n Elemente des Streams s
(define (stream-elems s n)
  (cond
    ((= n 0) (list (head s)))
    (else
     (append (list (head s)) (stream-elems (tail s) (- n 1))))))
</code>
Zur Aufzählung verwenden wir auch hier wieder Streams und erwarten natürlich nur ungeraden Quadratzahlen:
<run id="4dbfcdea47ec7">
;Gibt die ersten 100 Elemente der Schnittmenge von M1 und M2 aus
(stream-elems g-stream 100)
</run>