Entscheidbarkeit und Aufzählbarkeit

Aus ProgrammingWiki

Archivierte Version vom 2012-03-27T19:40:26+00:00. Aktuelle Version

Entscheidbarkeit

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

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

Die Menge der Primzahlen ist aufzählbar unendlich:

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

(f 31)

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)

Die charakteristischen Funktion chi_primzahlen ist berechenbar:

(chi_primzahl 4)

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)

(chi_primzahlwoerter "30")

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.

(semi-chi primzahlwoerter "31")

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 ungerade_zahlen (generiere_aufzaehlbare_menge (lambda (n) (+ (* 2 n) 1))))

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

Entscheidbarkeit und Aufzählbarkeit