Berechenbarkeitstheorie/Entscheidbarkeit und Aufzählbarkeit
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>FLACI_c97gpsjc5dyr</language>
==Entscheidbarkeit, Charakteristische Funktion, Aufzählbarkeit==
<code id="4f71929a79c30" hidden>
;;; 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))))
</code>
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.
<code id="4f6cafece05e6">
(define chi-laenge3
(lambda (w)
(if (member w '("aaa" "aab" "aba" "baa" "abb" "bab" "bba" "bbb"))
#t
#f)))
</code>
<run id="4f6cafece065c">(chi-laenge3 "abb")</run>
<code id="4f7468bcedfb9" hidden>
(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))
</code>
Beispiel: Wörter über $\{a,b\}^*$, die mit $a$ beginnen. Das ist eine abzählbar unendliche Menge. Sie ist entscheidbar.
<code id="4f6ca9bc8928d">
(define chi-a
(lambda (w)
(char=? (string-ref w 0) #\a)))
</code>
<run id="4f6ca9bc89383">
(chi-a "ababaab")
</run>
Die Menge der Fibonacci-Zahlen ist aufzählbar unendlich:
<run id="4f7468bcee0c1">(menge-bis FIBS 30)</run>
Die Menge der Primzahlen ist aufzählbar unendlich:
<code id="4f71666af239c" hidden>
(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)))))
</code>
<code id="4f71666af2b1e">
(define f
(lambda (n)
(if (prim? n)
n
2)))
</code>
<run id="4f71666af3428">(f 31)</run>
Offensichtlich ist f surjektiv und berechenbar.
Wir verwenden f, um die unendliche Menge der Primzahlen zu erzeugen:
<code id="4f721421bc21e">
(define primzahlen (generiere_aufzaehlbare_menge f))
</code>
Man kann sich das Anfangsstück einer aufzählbar unendlichen Menge anschauen:
<run id="4f721421bc4ef">
(menge-bis primzahlen 30)
</run>
Die charakteristischen Funktion <tt>chi_primzahlen</tt> ist berechenbar:
<code id="4f721421bc2b0" hidden>
(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))))
</code>
<run id="4f721421bc574">(chi_primzahl 4)</run>
Analog geht das Ganze auch mit Zahlwörtern, was auf Wortfunktionen $A^*\mapsto A^*$ hinausläuft.
<code id="4f721421bc322">
(define primzahlwoerter (generiere_aufzaehlbare_wortmenge f))
</code>
<run id="4f721421bc5fb">(menge-bis primzahlwoerter 20)</run>
<code id="4f721421bc3a2" hidden>
(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))))
</code>
<run id="4f721421bc695">(chi_primzahlwoerter "30")</run>
=== Semi-Entscheidbarkeit ===
Wir stellen (im Hintergrund) die Prozedur <tt>semi-chi</tt> bereit. Sie berechnet die semi-charakteristische Funktion. Dies gelingt natürlich auch für die Primzahlen.
<code id="4f721421bc42f" hidden>
(define semi-chi
(lambda (m w)
(letrec
((helfer
(lambda (stm)
(if (string=? w (stream-car stm))
#t
(helfer (stream-cdr stm))))))
(helfer m))))
</code>
<run id="4f721421bc730">(semi-chi primzahlwoerter "31")</run>
Wählt man ein Zahlwort, das eine Nicht-Primzahl repräsentiert, muss die Berechnung von außen abgebrochen werden.
=== Vereinigung zweier aufzählbarer Mengen ===
<code id="4f7217a9ad719" hidden>
(define stream-union
(lambda (stm1 stm2)
(stream-cons
(stream-car stm1)
(stream-cons
(stream-car stm2)
(stream-union (stream-cdr stm1) (stream-cdr stm2))))))
</code>
<code id="4f7217a9ad814" hidden>
(define ungerade_zahlen (generiere_aufzaehlbare_menge (lambda (n) (+ (* 2 n) 1))))
</code>
<run id="4f72182a99d8b">(menge-bis ungerade_zahlen 30)</run>
<run id="4f7217a9ad947">(menge-bis (stream-union ungerade_zahlen primzahlen) 40)</run>
An der Ausgabe erkennt man das Reißverschlussprinzip.
=== Durchschnittsmenge zweier aufzählbarer Mengen ===
<code id="4f72199497564" hidden>
;; 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)
</code>
Die Menge der Primzahlen und die Fibonacci-Zahlen:
<run id="4f7468bcee17c">(menge-bis primzahlen 25)</run>
<run id="4f746b5985b51">(menge-bis FIBS 25)</run>
<run id="4f7468bcee215">
(menge-bis (stream-intersection primzahlen FIBS) 6)
</run>