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.

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

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