Berechenbarkeitstheorie

Aus ProgrammingWiki

Archivierte Version vom 2012-03-10T11:25:02+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

Primzahlzwillinge

F(n) = p,\text{ mit } p>n,\ p,p+2\text{ sind Primzahlen}.

(F 29)

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