Berechenbarkeitstheorie/Entscheidbarkeit und Aufzählbarkeit

Wiki-Quelltext dieser Seite.

<language>Scheme</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>


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 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)))))))
      (cond
        ((= n 1) #f)
        ((= n 2) #t)
        ((= (remainder n 2) 0) #f)
        (else
         (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.