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

<code>
(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 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>
(define quad-stream (stream-map g natzahlen))
</code>

Damit können wir <math>f</math> wie folgt implementieren:
<code>
(define f
  (lambda (n)
    (if (chi-endlich (g n) (stream->list quad-stream (+ n 1)))
        (g n)
        4)))
</code>
<run>(f 5)</run>
<run>(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.

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

<math>\chi_{M_1,M_2}</math>

<code>
(define chi
  (lambda (i m1 m2)
    (if (chi-strich i m1)
        #t
        (if (chi-strich i m2)
            #f
            'fehler))))
</code>
<run>(chi 25 quad-stream natzahlen)</run>

Vorsicht bei:
<run>(chi 26 quad-stream natzahlen)</run>