BuK/IIm11/Studenten/simawiel/ue3

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
== Aufgabe 3: ÜA: Zeigen Sie, dass die Menge der geraden Zahlen G eine aufzählbare Menge ist. ==

'''Gegeben:'''

aufzählbar: abzählbar + berechenbar

abzählbar: $\exists f$: $\N \mapsto G$, $G$ sei die Menge der geraden Zahlen

$f$: surjektiv

berechenbar: Es gibt einen Algorithmus für $f$

Funktion: 
$f(n) =  \left\{\begin{array}{cc}
n; wenn\ 2|n\\
-1 \cdot (n + 1); sonst\\
\end{array}\right.$


Algorithmus:
<code id="4f7afc9e7e9b0">(define f
  (lambda (n)
    (if (= (modulo n 2) 0)
      n
      (* (+ n 1) -1)
    )
  )
)</code>
<run id="4f7afc9e7ea18">
(f 1)
</run>

== ÜA: Zeigen Sie, dass die Menge der Primzahlen P aufzählbar ist. ==