BuK/IIm10/BuK-Übung03 G2

Wiki-Quelltext dieser Seite.

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

==Lösung==
Wenn <math>\wp(A^*)</math> abzählbar unendlich wäre, so müsste eine bijektive Abbildung auf die natürlichen Zahlen erfolgen können.
Bijektiv bedeutet in diesem Fall, dass jedem Element aus <math>N</math> '''genau ein''' Element aus <math>\wp(A^*)</math> zugeordnet wird.

Die Menge <math>\wp(A^*)</math> wird über <math>A^*</math> gebildet. Unter der Annahme, dass <math>\wp(A^*)</math> abzählbar unendlich ist, müsste man also
zuerst die natürlichen Zahlen auf <math>A^*</math> abbilden können und anschließend <math>A^*</math> auf <math>\wp(A^*)</math>.

[[Datei:Abbildung.png]]

Für eine bijektive Abbildung von <math>N</math> auf <math>\wp(A^*)</math> müssten also alle drei Mengen gleichmächtig, im konkreten Fall also abzählbar unendlich sein.
Dass <math>N</math> abzählbar unendlich ist steht außer Frage. Dass <math>A^*</math> ebenfalls abzählbar unendlich ist, wurde in [[BuK/IIm10/BuK-Übung02 G2#Aufgabe 2| Übung 2]] nachgewiesen.

Wie kann nun die Mächtigkeit von <math>\wp(A^*)</math> bestimmt werden?
Die Potenzmenge ist folgendermaßen definiert: <math>\wp(X) := \{U | U \subseteq X\}</math>.
Die Menge <math>A^*</math> besteht aus den Wörtern <math>w_1, w_2, \dots, w_k</math>.
Daraus folgt, dass <math>\wp(A^*)</math> für jedes <math>w_i</math> aus <math>A^*</math> ein Element der Form <math>\{w_i\}</math> enthält.
Zusätzlich enthält <math>\wp(A^*)</math> aber unter Anderem auch <math>\{\}</math>. Das allein reicht aus, um sagen zu können <math>|\wp(A)| > |A|</math>.

Somit ist bewiesen, dass es keine bijektive Abbildung von <math>A</math> auf <math>\wp(A^*)</math> geben kann und somit auch keine von
<math>N</math> auf <math>\wp(A^*)</math>. Demzufolge ist <math>\wp(A^*)</math> eine überabzählbar unendliche Menge.

==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><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 und berechenbar sein.
Dazu benötigen wir die sogenannte Aufzählfunktion <math>g</math> für die Menge der Quadratzahlen.

<code id="4d94429a0e930">
(define g
  (lambda (n)
    (* n n)))
</code>

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

Die Menge <math>M</math> erzeugen wir mit Hilfe von Streams.

<code id="4d94429a0e9ca" hidden>
(define stream-car car)

(define stream-cdr
  (lambda (s)
    (force (cdr s))))

(define-syntax stream-cons
  (syntax-rules ()
    ((_ head tail) (cons head (delay tail)))))

(define stream?
  (lambda (s)
    (and (pair? s)(promise? (cdr s)))))

(define make-stream 
  (lambda (seed proc)
    (letrec 
      ((stream-builder
         (lambda (n)
           (stream-cons n (stream-builder (proc n))))))
      (stream-builder seed))))

(define *the-end-of-stream-tag*
  (make-stream
   "eos"
   (lambda (str) str)))
  
(define stream-item
  (lambda (str k)
    (if (= k 0)
      (stream-car str)
      (stream-item (stream-cdr str) (- k 1)))))

(define stream->list
  (lambda (str n)
    (if (<= n 0)
      '()
      (cons 
        (stream-car str) 
        (stream->list (stream-cdr str) (- n 1))))))

(define stream-map
  (lambda (f s)
    (stream-cons
     (f (stream-car s))
     (stream-map f (stream-cdr s)))))

(define print-stream
  (lambda (stm n)
    (cond
     ((<= n 0) (display "...\n"))
     (else
      (display (stream-car stm))
      (display ", ")
      (print-stream (stream-cdr stm) (- n 1))))))


(define nat-stream
  (lambda (start)
    (stream-cons start (nat-stream (+ start 1)))))

(define natzahlen (nat-stream 0))
</code>

<code id="4d94429a0ea50">
(define quad-stream (stream-map g natzahlen))
</code>

Damit können wir <math>f</math> wie folgt implementieren:
<code id="4d94429a0ead6">
(define f
  (lambda (n)
    (if (chi-endlich (g n) (stream->list quad-stream (+ n 1)))
        (g n)
        4)))
</code>
<run id="4d94429a0ec96">(f 5)</run>
<run id="4d94429a0ed53">(f 3.789)</run>

==Aufgabe==
Schreiben Sie eine Scheme-Prozedur, die die Menge der Quadratzahlen relativ zur Menge
der natürlichen Zahlen semi-entscheidet.

Hinweis: Implementieren Sie eine Prozedur für die (allgemeingültige) <math>\chi^'_M</math> und wenden
Sie sie auf die Menge (stream) der natürlichen Zahlen an. Überlegen Sie sich vor dem
Aufruf genau, welche Ausgabe Sie erwarten.


==Lösung==
<math>\chi^'_M</math>
<code id="4d942a31af109">
(define chi-strich
  (lambda (w m)
    (if (string=? w (stream-car m))
        #t
        (chi-strich w (stream-cdr m)))))
</code>

<code id="4d94429a0eb5a">
(define quad-stream2 
  (stream-map (lambda (i) (number->string i)) quad-stream))

(define natzahlen2
  (stream-map (lambda (i) (number->string i)) natzahlen))

(define quadRelZuNat
  (lambda (i)
    (if (chi-strich (number->string i) quad-stream2)
        #t
        (if (chi-strich (number->string i) natzahlen2)
            #f
            'fehler))))
</code>
<run id="4d94429a0edd4">(quadRelZuNat 4)</run>

Vorsich: Der folgende Aufruf stoppt nicht!
<run id="4d94429a0ee78">(quadRelZuNat 5)</run>

Um <math>\text{quadRelZuNat}</math> stoppen zu lassen verwenden wir weiter oben definierte Prozeduren.

<code id="4d94429a0ebbd">
(define quadRelZuNat2
  (lambda (i)
    (if (chi-endlich i (stream->list quad-stream (+ i 1)))
        #t
        (if (chi-strich (number->string i) natzahlen2)
            #f
            'fehler))))
</code>

<run id="4d94429a0ef1d">(quadRelZuNat2 5)</run>