BuK/IIm10/BuK-Übung05 G1
Aus ProgrammingWiki
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>.
"Kann man jede beliebige partielle Funktion <math>f_partiell</math> zu einer (zugehörigen) totalen <math>f_total</math> umkonstruieren? Genauer: Gibt es eine Prozedur <math>f_{totalmacher}</math>, die eine (partielle) Funktion <math>f_partiell</math> nimmt und die zugehörige totale <math>f_total</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>