Sätze und Zusammenhänge

STREAMS - Implementation mit verzoegerter Evaluation (delay, force)

Selektoren

(define stream-car

 (lambda (s)
   (car (force s))))

(define stream-cdr

 (lambda (s)
   (cdr (force s))))

Konstruktoren

(define-syntax stream-cons

 (syntax-rules ()
   ((_ x str) (delay (cons x str)))))

(define make-stream

 (lambda (seed proc)
   (letrec 
       ((stream-builder
         (lambda (n)
           (delay (cons n (stream-builder (proc n)))))))
     (stream-builder seed))))

Operationen mit streams

(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 str)
   (delay
     (cons
      (f (stream-car str))
      (stream-map f (stream-cdr str))))))

(define print-stream

 (lambda (str items)
   (if (<= items 0)
       (begin
         (display "...")(newline))
       (begin
         (write (stream-car str))
         (display ", ")
         (print-stream (stream-cdr str)(- items 1))))))

nat_zahlen

(display (stream->list nat_zahlen 20))

nat_zahlen

(display (stream->list (stream-map (lambda (i) (* 10 i)) nat_zahlen) 10))

--- Ende streams ---

Aufzaehlbare Mengen

(define nat_zahlen (make-stream 0 (lambda (n) (+ n 1))))

(define menge-bis print-stream) ; angepasster Prozedurnamen

(define generiere_aufzaehlbare_menge

 (lambda (f)
   (stream-map f nat_zahlen)))

(define generiere_aufzaehlbare_wortmenge

 (lambda (f)
   (stream-map number->string (stream-map f nat_zahlen))))

Aufzählbarkeit und Semi-Entscheidbarkeit

Abzählbarkeit und Aufzählbarkeit

Paarungsfunktionen usw.

Entscheidbarkeit und Aufzählbarkeit

Satz: Eine Menge M, mit M\subseteq A^*, ist entscheidbar genau dann, wenn M und A^*\setminus M (Komplementmenge) aufzählbare Menge sind.

Wir wollen den Beweis des Teils "Wenn M und A^*\setminus M aufzählbare Mengen sind, dann ist M eine entscheidbare Menge." mit einem ausführbaren Beispiel illustrieren.

Wir wählen für f die Aufzählprozedur für die ungeraden Zahlen und für g die Aufzählprozedur für die geraden Zahlen. Damit erzeugen wir die betrachteten Mengen M und A^*\setminus M.

Von beiden Mengen schauen wir uns jeweils 10 Elemente an.

Wie man sieht, haben wir es mit Mengen von Zahlwörtern zu tun.

Die Prozedure für \chi_M wurde so konstruiert, wie im Beweis angegeben. Erproben Sie selbst einige Aufrufbeispiele mit selbstgewählten Wörtern aus A^*, also Wörtern natürlicher Zahlen.