Berechenbarkeitstheorie/Vorbereitungen

Wiki-Quelltext dieser Seite.

<language>SchemeJS</language>
==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>


== Intuitiver Berechenbarkeitsbegriff ==

===Primzahlzwillinge===

Man weiß nicht, ob es tatsächlich unendlich viel gibt.

<code id="6540145977ae7" hidden>
(define prim?
  (lambda (n)
    (letrec 
        ((helper
          (lambda (teiler)
            (cond
              ((= 1 teiler) #t)
              ((zero? (modulo n teiler)) #f)
              (else
               (helper (- teiler 1)))))))
      (helper (- n 1)))))

(define F
  (lambda (n)
    (letrec
        ((helper
          (lambda (p)
            (if (and (prim? p)(prim? (+ p 2)))
                p
                (helper (+ p 1))))))
      (helper (+ n 1)))))
</code>

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

<run id="6540145977b42">(F 27)</run>


===Collatz-Folge===

Man weiß nicht, ob die Folge für jede beliebige Startzahl bei 1 endet.

<code id="4f5a2d18cd8c3">
(define collatz
  (lambda (a)
    (cond
      ((= a 1) '(1))
      ((even? a)(cons a (collatz (/ a 2))))
      (else
       (cons a (collatz (+ (* 3 a) 1)))))))
</code>
<run id="4f5a2d18cd934">(collatz 7)</run>