Entscheidbarkeit und Aufzählbarkeit

Aus ProgrammingWiki

Inhaltsverzeichnis 1 Entscheidbarkeit, Charakteristische Funktion, Aufzählbarkeit 1.1 Semi-Entscheidbarkeit 1.2 Vereinigung zweier aufzählbarer Mengen 1.3 Durchschnittsmenge zweier aufzählbarer Mengen

Entscheidbarkeit, Charakteristische Funktion, Aufzählbarkeit

;;; 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))))

Beispiel: Wörter der Länge 3 über $\{a,b\}^*$

Die zu charakterisierende Menge ist endlich, denn es gibt nur $2^3=8$ solche Wörter.

(define chi-laenge3 (lambda (w) (if (member w '("aaa" "aab" "aba" "baa" "abb" "bab" "bba" "bbb")) #t #f)))

(chi-laenge3 "abb")

ausführen

(define fib (lambda (n) (letrec ((helper (lambda (a b n) (cond ((= n 0) 0) ((= n 1) b) (else (helper b (+ a b) (- n 1))))))) (helper 0 1 n)))) (define FIBS (generiere_aufzaehlbare_menge fib))

Beispiel: Wörter über $\{a,b\}^*$, die mit $a$ beginnen. Das ist eine abzählbar unendliche Menge. Sie ist entscheidbar.

(define chi-a (lambda (w) (char=? (string-ref w 0) #\a)))

(chi-a "ababaab")

ausführen

Die Menge der Fibonacci-Zahlen ist aufzählbar unendlich:

(menge-bis FIBS 30)

ausführen

Die Menge der Primzahlen ist aufzählbar unendlich:

(define prim? (lambda (n) (letrec ((helfer (lambda (t) (cond ((> t (sqrt n)) #t) ((= (remainder n t) 0) #f) (else (helfer (+ t 2))))))) (if (or (< n 2) (even? n)) #f (helfer 3)))))

(define f (lambda (n) (if (prim? n) n 2)))

(f 31)

ausführen

Offensichtlich ist f surjektiv und berechenbar.

Wir verwenden f, um die unendliche Menge der Primzahlen zu erzeugen:

(define primzahlen (generiere_aufzaehlbare_menge f))

Man kann sich das Anfangsstück einer aufzählbar unendlichen Menge anschauen:

(menge-bis primzahlen 30)

ausführen

Die charakteristischen Funktion chi_primzahlen ist berechenbar:

(define chi_primzahl (lambda (n) (letrec ((helfer (lambda (stm) (cond ((> (stream-car stm) n) #f) ((= n (stream-car stm)) #t) (else (helfer (stream-cdr stm))))))) (helfer primzahlen))))

(chi_primzahl 4)

ausführen

Analog geht das Ganze auch mit Zahlwörtern, was auf Wortfunktionen $A^*\mapsto A^*$ hinausläuft.

(define primzahlwoerter (generiere_aufzaehlbare_wortmenge f))

(menge-bis primzahlwoerter 20)

ausführen

(define chi_primzahlwoerter (lambda (n) (letrec ((helfer (lambda (stm) (cond ((> (string->number (stream-car stm)) (string->number n)) #f) ((string=? n (stream-car stm)) #t) (else (helfer (stream-cdr stm))))))) (helfer primzahlwoerter))))

(chi_primzahlwoerter "30")

ausführen

Semi-Entscheidbarkeit

Wir stellen (im Hintergrund) die Prozedur semi-chi bereit. Sie berechnet die semi-charakteristische Funktion. Dies gelingt natürlich auch für die Primzahlen.

(define semi-chi (lambda (m w) (letrec ((helfer (lambda (stm) (if (string=? w (stream-car stm)) #t (helfer (stream-cdr stm)))))) (helfer m))))

(semi-chi primzahlwoerter "31")

ausführen

Wählt man ein Zahlwort, das eine Nicht-Primzahl repräsentiert, muss die Berechnung von außen abgebrochen werden.

Vereinigung zweier aufzählbarer Mengen

(define stream-union (lambda (stm1 stm2) (stream-cons (stream-car stm1) (stream-cons (stream-car stm2) (stream-union (stream-cdr stm1) (stream-cdr stm2))))))

(define ungerade_zahlen (generiere_aufzaehlbare_menge (lambda (n) (+ (* 2 n) 1))))

(menge-bis ungerade_zahlen 30)

ausführen

(menge-bis (stream-union ungerade_zahlen primzahlen) 40)

ausführen

An der Ausgabe erkennt man das Reißverschlussprinzip.

Durchschnittsmenge zweier aufzählbarer Mengen

;; mutual recursion ; Fall 1: M1 schnitt M2 = leere Menge ; Fall 2: Es gibt (wenigstens) ein Element a mit a in M1 schnitt M2 ; f1 schaut in Pool2 nach, ob f1(n) enthalten ist, und beliefert Pool1. ; f2 schaut in Pool1 nach, ob f2(n) enthalten ist, und beliefert Pool2. (define stream-intersection (lambda (m1 m2) (letrec ((intersec-helper1 ; f1 (lambda (m1 m2 pool1 pool2) ; (printf "Pool1: ~a Pool2: ~a~n" pool1 pool2) (let ((x (stream-car m1))) (if (member x pool2) (stream-cons x (intersec-helper2 (stream-cdr m1) m2 pool1 pool2)) (intersec-helper2 (stream-cdr m1) m2 (cons x pool1) pool2))))) (intersec-helper2 ; f2 (lambda (m1 m2 pool1 pool2) (let ((x (stream-car m2))) (if (member x pool1) (stream-cons x (intersec-helper1 m1 (stream-cdr m2) pool1 pool2)) (intersec-helper1 m1 (stream-cdr m2) pool1 (cons x pool2))))))) (intersec-helper1 m1 m2 '()'())))) (define ungerade_zahlen (generiere_aufzaehlbare_menge (lambda (n) (+ (* 2 n) 1)))) ;(menge-bis ungerade_zahlen 15) ;(menge-bis FIBS 15)

Die Menge der Primzahlen und die Fibonacci-Zahlen:

(menge-bis primzahlen 25)

ausführen

(menge-bis FIBS 25)

ausführen

(menge-bis (stream-intersection primzahlen FIBS) 6)

ausführen