Berechenbarkeitstheorie

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
== Begleit-PW zum Buch "Einführung in die Berechenbarkeitstheorie" von CW ==

=== Kapitel 2: Intuitiver Berechenbarkeitsbegriff ===

==== Endliche Mengen ====

Die Mächtigkeit endlicher Mengen ergibt sich aus deren Kardinalität. Man kann sie rekursiv definieren als 
\[ card(M) =
\left\{
  \begin{array}{cl}
    0, & \hbox{wenn } M=\emptyset \\
    1+card(\{a_2,a_3,\ldots,a_n\}), & \hbox{wenn } M=\{a_1,a_2,a_3,\ldots,a_n\}
  \end{array}
\right. \]

Dies lässt sich leicht in ein Programm umsetzen:
<code id="4f5a2647cd148">
(define card
  (lambda (m)
    (if (null? m)
      0
      (+ 1 (card (cdr m))))))
</code>
<run id="4f5a2647cd1ce">(card '(y z u a k w))</run>


==== Collatz-Folge ====

<code id="4f5a2d18cd8c3">
(define collatz
  (lambda (a)
    (cond
      ((= a 1) '(1))
      ((even? a)(cons a (collatz (/ a 2))))
      (else
       (cons a (collatz (+ (* 3 a) 1)))))))
</code>
<run id="4f5a2d18cd934">(collatz 7)</run>