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>