Berechenbarkeitstheorie

Aus ProgrammingWiki

Archivierte Version vom 2012-03-09T16:42:03+00:00. Aktuelle Version

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

Vorbereitungen

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:

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

(card '(y z u a k w))

Intuitiver Berechenbarkeitsbegriff

Collatz-Folge

(define collatz
  (lambda (a)
    (cond
      ((= a 1) '(1))
      ((even? a)(cons a (collatz (/ a 2))))
      (else
       (cons a (collatz (+ (* 3 a) 1)))))))

(collatz 7)

Berechenbarkeitstheorie

Vorbereitungen

Intuitiver Berechenbarkeitsbegriff

Suche