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 g$: $\N \mapsto G$, $G$ sei die Menge der geraden Zahlen

$g$: surjektiv

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

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


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

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

'''Gegeben:'''

aufzählbar: abzählbar + berechenbar

abzählbar: $\exists p$: $\N \mapsto P$, $P$ sei die Menge der Primzahlen

$p$: surjektiv

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

Funktion: