Entscheidbarkeit und Aufzählbarkeit

Entscheidbarkeit, Charakteristische Funktion, Aufzählbarkeit

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.

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

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

Die Menge der Primzahlen ist aufzählbar unendlich:

Offensichtlich ist f surjektiv und berechenbar.

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

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

Die charakteristischen Funktion chi_primzahlen ist berechenbar:

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

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.

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

Vereinigung zweier aufzählbarer Mengen

An der Ausgabe erkennt man das Reißverschlussprinzip.

Die Menge der Primzahlen: