BuK/IIm10/BuK-Übung04 G2

Wiki-Quelltext dieser Seite.

<language>FLACI_c97gpsjc5dyr</language>
=Aufzählbarkeit und Entscheidbarkeit=

== Aufgabe ==
Drücken Sie den Beweis des folgenden Satzes mit Racket aus.
Wenn <math>M</math> eine aufzählbar unendliche Menge ist, dann ist <math>M</math> semi-entscheidbar.

== Lösung ==
<math>M</math> ist eine aufzählbar unendliche Menge und damit existiert eine Funktion <math>f:\mathbb{N}\rightarrow{}M</math>, die surjektiv und berechenbar ist und die Menge <math>M</math> aufzählt. <br>
<math>M</math> ist semi-entscheidbar, wenn eine Funktion <math>\chi'_M:A^{\ast}\rightarrow{}\mathbb{B}</math> existiert, die berechenbar ist.<br>
Die folgende Umsetzung in Racket beweist, dass <math>M</math> semi-entscheidbar ist, wenn die Aufzählfunktion <math>f</math> gegeben ist.
<code id="123">
(define chi-strich
  (lambda (wort)
    (letrec 
        ((suche-in-chi 
          (lambda (i) (if (string=? wort (f i))
                          #t
                          (suche-in-chi (+ i 1))))))      
      (suche-in-chi 0))))
</code>

=== Beispiel ===
Gegeben sei das Alphabet ("a" "b" ... "z").
Die Menge <math>M</math> ist die Menge der Wörter, die sich aus der Verkettung mit dem Buchstaben "a" bilden lassen. Die folgende Funktion <math>f</math> zählt diese Menge auf. 
<code id="4ded0dd08707f">
(define f
  (lambda (i) (make-string i #\a)))
</code>

<run id="4ded0dd087100">
(f 3)
</run>

Der Aufruf der Funktion <math>\chi'_M</math> berechnet, ob das gegebene Wort in <math>M</math> enthalten ist.
<run id="4ded0dd087160">
(chi-strich "aaaaa")
</run>
Wird ein Wort aus <math>A^{\ast}\backslash{}M</math> als Parameter übergeben, so stoppt die Berechnung nicht.
<run id="4ded0dd0871ba">
(chi-strich "ab")
</run>

= Entscheidbarkeit und Aufzählbarkeit =

== Aufgabe ==
Beweisen Sie: Wenn <math>M</math> entscheidbar ist, dann sind <math>M</math> und <math>A^{\ast}\backslash{}M</math> aufzählbar. Illustrieren Sie anschließend mit Racket.


== Lösung ==
Entscheidbarkeit bedeutet, es exisitert eine (totale) charakteristische Funktion <math>\chi_{M_1,M_2}</math>, welche ein Wort <math>w</math> aus <math>M_2</math> als Eingabe erwartet und "1" zurückgibt, falls <math>w \in M_1</math> und "0", falls <math>w \in M_2\backslash{}M_1</math>.

Das heißt wir können davon ausgehen, dass die Funktion <math>\chi_{M,A^{\ast}}(w)</math> exisitert.

Die Mengen <math>M</math> und <math>A^{\ast}\backslash{}M</math> sind aufzählbar, wenn die surjektiven, berechenbaren Funktionen <math>f_M: \mathbb{N} \mapsto M</math>
und <math>f_{A^{\ast}\backslash{}M}: \mathbb{N} \mapsto A^{\ast}\backslash{}M</math> existieren.

Diese Aufzählfunktionen können unter Verwendung von <math>\chi_{M,A^{\ast}}(w)</math> definiert werden. Dafür benötigen wir noch eine Funktion <math>g</math>, welche die Menge <math>A^{\ast}</math> aufzählt.

Zur Illustration legen wir fest, dass <math>A^{\ast}</math> die Menge der natürlichen Zahlwörter, <math>M</math> die Menge der Zahlwörter für die geraden Zahlen und <math>A^{\ast}\backslash{}M</math> die Menge der Zahlwörter für die ungeraden Zahlen darstellen.

<code id="4dac2a35c519c">
(define f-m
  (lambda (i)
    (if (chi? (g i))
      (g i)
      a)))
</code>

<code id="4dac2a35c51ff">
(define f-m2
  (lambda (i)
    (if (chi? (g i))
      a
      (g i))))
</code>

= Semi-Entscheidbarkeit =
== Aufgabe ==
Zeigen Sie auf der Basis der Semi-Entscheidbarkeit, dass wenn <math>M</math> und <math>A^{\ast}\backslash{}M</math> aufzählbar sind, <math>M</math> entscheidbar ist. Repräsentieren Sie den Beweis anschließend mit Racket.
Verwenden Sie die entwickelten Racket-Prozeduren für folgendes Beispiel: <math>A^{\ast}</math> ist die Menge der natürlichen Zahlwörter, <math>M</math> die Menge der Zahlwörter für die geraden Zahlen und <math>A^{\ast}\backslash{}M</math> die Zahlwörter für die ungeraden Zahlen.

== Lösung ==

Die Mengen <math>M</math> und <math>A^{\ast}\backslash{}M</math> sind aufzählbar. D.h. es existiert eine Funktion <math>f_M:\mathbb{N}\rightarrow{}M</math> sowie eine Funktion <math>f_{M\backslash{}A^{\ast}}:\mathbb{N}\rightarrow{}M\backslash{}A^{\ast}</math>. <math>M</math> ist entscheidbar wenn <math>\chi_M:A^{\ast}\rightarrow{}\mathbb{B}</math> eine berechenbare Funktion ist.<br>
Die folgende Racket-Funktion beweist, dass <math>M</math> entscheidbar ist. Die Funktion ''f-m'' ist die Aufzählfunktion der Menge <math>M</math> und die Funktion ''f-m2'' ist die Aufzählfunktion der Komplementärmenge <math>M\backslash{}A^{\ast}</math>.
<code id="576a35ec25a7d">
(define chi
  (lambda (wort)
    (letrec 
        ((suche-in-chi 
          (lambda (i) (if (string=? wort (f-m i))
                          #t
                          (if (string=? wort (f-m2 i))
                              #f
                              (suche-in-chi (+ i 1)))))))      
      (suche-in-chi 1))))
</code>
=== Beispiel ===
Wie oben in der Aufgabenstellung ist <math>A^{\ast}</math> die Menge aller Zahlwörter der natürlichen Zahlen. <math>M</math> ist die Menger der Zahlwörter der geraden Zahlen und wird aufgezählt durch:
<code id="576a35ec25af2">
(define f-m
  (lambda (i) 
    (number->string (* i 2) 10)))
</code>
Die Komplementärmenge <math>M\backslash{}A^{\ast}</math> ist demzufolge die Menge der Zahlwörter der ungeraden Zahlen und wird aufgezählt durch:
<code id="576a35ec25b65">
(define f-m2
  (lambda (i) 
    (number->string (- (* i 2) 1) 10)))
</code>
Die Funktion <math>\chi_M</math> berechnet für jedes Zahlwort einen Rückgabewert (Wahr oder Falsch).
<run id="576a35ec25c68">(chi "12")</run>