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.

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

ue4