Berechenbarkeitstheorie

Aus ProgrammingWiki

Archivierte Version vom 2012-03-09T15:48:24+00:00. Aktuelle Version

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:

(define card
  (lambda (m)
    (if (null? m)
      0
      (+ 1 (card (cdr m))))))

(card '(aks "jssaa" 1 882 #\s)

Berechenbarkeitstheorie

Begleit-PW zum Buch "Einführung in die Berechenbarkeitstheorie" von CW

Kapitel 2: Intuitiver Berechenbarkeitsbegriff

Endliche Mengen

Suche