Berechenbarkeitstheorie/Turing-Berechenbarkeit und Churchsche These

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
==Merkwürdige aber berechenbare Funktionen==

===Collatz-Folge===

<code id="4f8a79406ab06" hidden>
(define collatz
  (lambda (n)
    (cond
      ((= n 1) '())
      ((even? (cons n (collatz (/ n 2))))
      (else
        (cons n (collatz (+ (* 3 n) 1)))))))
</code>

<run id="4f8a79406abff">(collatz 7)</run>

===Für alle Argumente undefinierte Funktion===

<code id="4f8a79406ab82" hidden>
(define nirgends-definiert
  (lambda (n)
    (nirgends-definiert n)))
</code>

<run id="4f8a79406ac79">(nirgends-definiert)</run>