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

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

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