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