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}{r@{,\; \mbox{wenn}\;}l}
            0 & M=\emptyset \\
                    1+card(\{a_2,a_3,\ldots,a_n\}) & 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 '(aks "jssaa" 1 882 #\s)</run>