BuK/IIm10/BuK-Übung03 G2

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
=Aufzählbarkeit und Entscheidbarkeit=
== Aufgabe ==
Zeigen Sie, dass <math>\varphi(A^*)</math> für ein beliebiges Alphabet A eine überabzählbar unendliche Menge
ist.

== Lösung ==
TODO

==Aufgabe==
Implementieren Sie eine Scheme-Prozedur chi-endlich, die eine natürliche Zahl n und
eine Liste L nimmt und entweder #t oder #f zurückgibt, je nachdem ob <math>n \in L</math> oder
<math>n \notin L</math> gilt.
Stellen Sie für den Entwurf von chi-endlich die erforderlichen Hilfsprozeduren bereit.




==Lösung==
<code id="4d9419c7bee51">
(define (chi-endlich? n ls) 
  (cond
    [(null? ls) #f]
    [(= n (car ls)) #t]
    [else (chi-endlich? n (cdr ls))]))</code>

<run id="4d9419c7beeb5">(chi-endlich? 5 '(1 19 7 23 6 12))</run>
<run id="4d941ca1c4377">(chi-endlich? 5 '(1 19 7 23 5 6 12))</run>

==Aufgabe==
Schreiben Sie eine Scheme-Prozedur, die die Menge der Quadratzahlen aufzählt.

<language>Scheme</language>
<language>Scheme</language>
==Lösung==
Man sagt <math>f</math> zählt <math>M</math> auf, wenn gilt:

<math>M \subseteq A^*</math><br>
<math>f</math> ist eine totale Funktion der Form <math>f: N \mapsto M</math><br>
<math>f</math> ist surjektiv und berechnbar und deren Wertebereich ist <math>M = {f(0), f(1), \dots}</math><br>

Dabei ist <math>M</math> die Menge der Quadratzahlen. Die Funktion <math>f</math> muss also eine surjektive Abbildung der natürlichen Zahlen <math>N</math> auf die Menge <math>M</math> vornehmen.

<math>f(n) = \begin{cases}g(n), & \text{wenn } g(n) \in M \\4, & \text{sonst}\end{cases}</math>

Dabei ist <math>g</math> eine Funktion, die überprüft, ob <math>n</math> eine Quadratzahl ist.

<code id="4d941fe7dc6b7">
(define g
  (lambda (n)
    (if (integer? (sqrt n))
        #t
        #f)))
</code>
<run id="4d941fe7dc748">(g 5)</run>
<run id="4d941fe7dc7ae">(g 25)</run>

<code id="4d941e94d6630">
(define f
  (lambda (n)
    (* n n)))
</code>
<run id="4d941e94d66c6">(f 5)</run>