ue4

Aus ProgrammingWiki

Inhaltsverzeichnis 1 Aufgabe 1 1.1 Teilaufgabe 1 1.2 Teilaufgabe 2 2 Aufgabe 3 3 Beweis von Satz 4, Teil 2

Aufgabe 1

Behauptung: Eine Menge M ist genau dann aufzählbar, wenn sie semi-entscheidbar ist.

Teilaufgabe 1

zu zeigen: Wenn $M$ aufzählbar, dann $M$ semi-entscheidbar.

Gegeben ist eine aufzählbare Menge. Daraus folgt, dass es eine Aufzählprozedur $f$ für $M$ gibt, welche die natürlichen Zahlen auf die Elemente von $M$ abbildet. $f : \N \mapsto M $

zu zeigen: $M$ ist semi-entscheidbar

Wenn $M$ semi-entscheidbar ist, dann gibt es eine Prozedur $\chi'_M$, die für ein Wort aus der Menge $M$ über dem Alphabet $A^*$ wahr zurückgibt, wenn das Wort in der Menge enthalten ist und ansonsten ewig weiter läuft. $\chi'_M(w) : A^* \mapsto \{\text{wahr}\}$

$$ \chi'_M(w) = \begin{cases} wahr; & \text{wenn } w \in M;\\ \bot; & sonst \end{cases} $$

Durch Verwendung der Prozedur $f$ kann entschieden werden, ob ein gegebenes Element in der Menge $M$ enthalten ist. Dabei wird $f$ für jedes $i$; mit $i \in \N$ aufgerufen, $f(0)$, $f(1)$, $f(2)$, ... Ergibt $f(i)$ das Wort, dann gibt $\chi'_M$ wahr zurück, ansonsten läuft die Prozedur ewig weiter.

$$ \chi'_M(w) = \begin{cases} wahr; & \text{wenn } f(i) = w; i \in \N;\\ \bot; & sonst \end{cases} $$

Teilaufgabe 2

zu zeigen: Wenn M semi-entscheidbar ist, dann ist M aufzählbar.

Aufgabe 3

Satz 3: Wenn die Menge $M$ entscheidbar ist, dann ist $M$ aufzählbar.

Beweis:

Es ist gegeben, dass $M$ entscheidbar ist. Damit ist $M$ auch semi-entscheidbar. Wie in Satz 1 bereits bewiesen wurde gilt, dass jede semi-entscheidbare Menge auch aufzählbar ist.

Beweis von Satz 4, Teil 2

Wenn $M$ und $A^*\setminus M$ aufzählbare Mengen sind, dann ist $M$ eine entscheidbare Menge.

;; Selektoren (define stream-car car) (define stream-cdr (lambda (stm) (force (cdr stm)))) ;; Konstruktoren (define-syntax stream-cons (syntax-rules () ((_ head tail) (cons head (delay tail))))) ;; Praedikat (define stream? (lambda (stm) (and (pair? stm)(promise? (cdr stm))))) ;; Operationen mit streams (define print-stream (lambda (stm n) (cond ((<= n 0) (display "...\n")) (else (display (stream-car stm)) (display ", ") (print-stream (stream-cdr stm) (- n 1)))))) (define stream-item (lambda (str k) (if (= k 0) (stream-car str) (stream-item (stream-cdr str) (- k 1)))))

(define generiere_aufzaehlbare_menge (lambda (fn) (letrec ((generator (lambda (index) (stream-cons (fn index) (generator (+ index 1))) ) )) (generator 0) ) ) ) (define menge-bis (lambda (menge anzahl) (print-stream menge anzahl) ) ) (define f (lambda (x) (+ (* 2 x) 1))) (define g (lambda (x) (* 2 x))) (define chi_M (lambda (w) (letrec ((suche (lambda (index) (cond [(= (string->number w) (f index)) #t] [(= (string->number w) (g index)) #f] [else (suche (+ index 1))] ) ) )) (suche 0) ) ) )

(define M (generiere_aufzaehlbare_menge f)) (define A*-M (generiere_aufzaehlbare_menge g)) (menge-bis M 10) (menge-bis A*-M 10) (chi_M "9199")

ausführen