BuK/IIm11/Studenten/sijeheid/ue4

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
== 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.
<code id="4f8ab187d464f" hidden>
;; 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)))))
</code>

<code id="4f8ab187d46b7">
(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)
    )
  )
)
</code>

<run id="4f8ab187d473c">
(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")
</run>