BuK/IIm11/BuK-Übung04

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
== Aufgabe 1 ==
Satz 1: Eine Menge M ist genau dann aufzählbar, wenn sie semi-entscheidbar ist.

=== Teilaufgabe 1 <tt>(Jens Heider, Daniel Tasche, Felix Nitsche, Stefan Lüttke)</tt> ===
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 <tt>(Tobias Salzmann, Ronald Krause, Robert Rosenberger, Stefan Scheumann)</tt> ===
ÜA: Vervollständigen Sie die Herleitung der Funktionen für x und y aus $z = π(x, y)$ und geben Sie als Beispiel die Ermittlung von x und y aus $z = π(1, 3) = 13$ an.

Herleitung der Funktionen für $x$ und $y$ aus $z = (x; y)$

$z =\frac{(x+y)(x+y+1)}{2} +y = t + y;$ <br />
$w = x + y;$ <br />
$x,y,z \in \N, w,t \in \R_{0}^{+}$


$t = z - y = \frac{w(w+1)}{2} = \frac{w^{2}+w}{2} $

Die Lösung von $w^{2} + w + 2t = 0$

$w_{1,2}=-\frac{p}{2} \pm \sqrt{\left(\frac{p}{2}\right)^2-q}$

$w_{1,2}=-\frac{1}{2} \pm \sqrt{\left(\frac{1}{2}\right)^2+2t}$

$w_{1,2}=-\frac{1}{2} \pm \sqrt{\frac{1}{4}+\frac{8t}{4}}$

$w_{1,2}=-\frac{1}{2} \pm \sqrt{\frac{1+8t}{4}}$

$w_{1,2}=-\frac{1}{2} \pm \frac{\sqrt{1+8t}}{2}$

für positives $w$ ist $w_1 = \frac{\sqrt{8t+1}-1}{2}$

<br />Außerdem gilt:<br />
$t \leq z $, weil $z=t+y$<br />
$z= t + w - x$, weil $z=t+y$ und $y=w-x$<br />
$z \leq t + w \leq t + w + 1 = \frac{w^{2}+w}{2} + w + 1 = \frac{(w+1)^{2} + (w+1)}{2}$

<br />Unter Verwendung von $z \leq  \frac{(w+1)^{2} + (w+1)}{2}$ können wir $w$ nach oben abschätzen.

$w = \frac{\sqrt{8t+1}-1}{2} \leq \frac{\sqrt{8z+1}-1}{2} \leq w+1 $

<br />Für $z$ wird $\frac{(w+1)^{2} + (w+1)}{2}$ eingesetzt:

$\frac{\sqrt{8\frac{(w+1)^{2} + (w+1)}{2}+1}-1}{2}$

$\frac{\sqrt{8\frac{w^2+3w+2}{2}+1}-1}{2}$

$\frac{\sqrt{\frac{8w^2+24w+16}{2}+1}-1}{2}$

$\frac{\sqrt{4w^2+12w+9}-1}{2}$ = $\frac{\sqrt{(2w+3)^2}-1}{2}$ = $\frac{2w+2}{2}$ = $\frac{2(w+1)}{2}$ = $w+1$

<br />Um die beiden natürlichen Zahlen x und y aus z zu gewinnen, ist
als erstes $w = \left\lfloor \frac{\sqrt{8z+1}-1}{2} \right\rfloor $ zu berechnen. Dann ergeben sich

$t = \frac{w(w+1)}{2}$ und
$y = z -t$ sowie 
$x = w - y$

'''Beispiel: Ermittelung von $x$ und $y$ aus $z=\pi(1,3) = 13$'''

$w = \left\lfloor \frac{\sqrt{8z+1}-1}{2} \right\rfloor = \left\lfloor \frac{\sqrt{8 \cdot 13+1}-1}{2} \right\rfloor = 4.623 = 4  $ 

$y=13-\frac{w(w+1)}{2} = 13-\frac{4(4+v1)}{2} = 13 - 10 = 3$

$x=w-y = 4 - 3 = 1$

'''Kritik an der Aufteilung Aufgabenstellung wird bis Dienstag 15:00 Uhr entgegen genommen und Bearbeitet ;-)'''

== Aufgabe 2 ==
Satz 2: Jede Teilmenge einer abzählbaren Menge ist abzählbar, aber nicht jede Teilmenge einer aufzählbaren Menge ist aufzählbar.

=== Teilaufgabe 1 - Beweis <tt>(Felix Nitsche, Stefan Lüttke)</tt> ===
zu zeigen: Jede Teilmenge $M_2$ einer abzählbaren Menge $M_1$ ist abzählbar.
Wenn $M_1$ eine abzählbare Menge ist, dann ist jede Teilmenge $M_2 \subseteq M_1$ abzählbar.


Da für $M_2 = \emptyset$ die Aussage offensichtlich zutrifft kann angenommen werden dass wenigstens ein Element $a \in  M_2$ existiert.


Für $M_1$ als abzählbare Menge existiert eine Funktion


$f(x) = n \in M_1$


welche die Menge der natürlichen Zahlen auf $ M_1 $ abbildet.


Dadurch kann man nun für $M_2$ die folgende Funktion angeben:


$
g(x) = \begin{cases}
f(x); & f(x) \in M_2;\\
a; & sonst
\end{cases}
$


Durch diese Funktion wird nun jedem Element der natürlichen Zahlen eindeutig ein Element der Menge $M_2$ zugeordnet, wodurch deren Abzählbarkeit bewiesen ist.

=== Teilaufgabe 2 - Indirekter Beweis <tt>(Max Wielsch, Raik Bieniek)</tt> ===

zu zeigen: Nicht jede Teilmenge $M_2$ einer aufzählbaren Menge $M_1$ ist aufzählbar.

oder: Wenn M1 eine aufzählbare Menge ist, dann gilt nicht für alle Teilmengen $M_2$ ⊆ $M_1$, dass sie aufzählbar sind.

Indirekter Beweis: Behauptung:  Wenn $M_1$ aufzählbar, dann jede Teilmenge $M_2$ ⊆ $M_1$ ist aufzählbar.

Gegeben:
* f: ℕ ↦ $M_1$; aufzählbar (surjektiv; berechenbar)
* $M_2$ ⊆ $M_1$
* Satz 1: Wenn $M_2$ entscheidbar ⇔ $M_2$ und $M_1 \setminus M_2$ aufzählbar.
* Satz 2: Wenn $M_2$ aufzählbar → dann ist $M_2$ semientscheidbar.

Gesucht:
* g: ℕ ↦ $M_2$; aufzählbar (surjektiv; berechenbar), d. h. es gilt Satz 1.

$g(x) =  \left\{\begin{array}{cc}
f(x), wenn\ f(x) ∈ M_2\\
a, wenn f(x) ∈ M1\setminus M_2\\
\end{array}\right.
$

laut Satz 2:

$Χ'_{M_2,M_1}(w) =  \left\{\begin{array}{cc}
wahr, (f(i) = w) ∈ M_2; für\ i\ von\ 0\ bis\ ∞\\
⊥, sonst\\
\end{array}\right.
$

$Χ_{M_2,M_1}(w) =  \left\{\begin{array}{cc}
wahr, (f(i) = w) ∈ M_2; für\ i\ von\ 0\ bis\ ∞\\
falsch, (f(i) = w) ∈ M_1\setminus M_2 \\
\end{array}\right.
$

$Χ'_{M_2,M_1}$ vs. $Χ_{M_2,M_1}$; entscheidbar ☇ semi-entscheidbar. → Behauptung falsch → Satz wahr.

<div align="right">$\square$</div>

== 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.

== Aufgabe 4 ==
Eine Menge M, mit $M \subseteq A^*$ ist entscheidbar genau dann, wenn M und $A^* \setminus $M aufzählbare Mengen sind.

=== Teilaufgabe 1 - Beweis Teil 1 <tt>(Ingo Körner, Christof Ochmann)</tt> ===
Hinrichtung des Satzes: Wenn M eine entscheidbare Menge ist, dann sind M und $A^*$\M aufzählbare Mengen.

Beweis:
Aus der Entscheidbarkeit von M folg semi-Entscheidbarkeit von M und \M.
Jede semi-entscheidbare Menge M ist aufzählbar. Es gibt eine Aufzählfunktion f für M. Sie wird auch Contorsche Paarungsfunktion genannt.

$$f(z) = \begin{cases}
g(x), & \text{wenn $\chi'_M$(g(x)) = wahr innerhalb von Zeit y};\\
a, & \text{wenn Proz. für $\chi'_M$(g(x)) innerhalb y ohne Ergebnis}.\\
\end{cases}$$
wobei a $\in$ M, wenn $M \neq \emptyset$

$$g(x) = \begin{cases}
w, & \text{w $\in$ M};\\
\perp, & \text{sonst}.\\
\end{cases}$$

=== Teilaufgabe 2 - Beweis Teil 2 <tt>(Tobias Salzmann, Ronald Krause)</tt> ===
[[Bild:Sitosalz_Entscheidbarkeit_aufzaehlbarkeit.png| miniatur | Abbildung]]

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

Da M und $A^*$\M aufzählbare Mengen sind, gibt es total berechenbare surjektive Funktionen für diese.

Für M lautet die Auzählfunktion $f: \N \mapsto M$:

$$f(n) = \begin{cases}
f(n), & \text{wenn } f(n) \in M;\\
a, & sonst
\end{cases}$$

'''Hinweis:''' $a \in M$ .

Für $A^*$\M lautet die Auzählfunktion $g: \N \mapsto A^*$\M:

$$g(n) = \begin{cases}
g(n), & \text{wenn } g(n) \in A^*\text{ \M};\\
b, & sonst
\end{cases}$$

'''Hinweis:''' $b \in A^*$\M .

==== Beweis ====

Da der Beweis erbracht werden soll, dass die Menge M entscheidbar ist, so muss eine total berechenbare Funktion $\chi_M$ existieren.

$$\chi_M(w) = \begin{cases}
wahr, & \text{wenn } w \in M;\\
falsch, & \text{wenn } w \in A^*\text{ \ M}
\end{cases}$$

Des Weiteren sollte es eine Prozedur ''chi'' geben, welche für jedes Wort $w$ in endlicher Zeit für ein $i$ mit w = f(i) oder w = g(i) findet.

Da die Schnittmenge von M und $A^*$\M eine leere Menge ist, kann es kein Wort ''w'' geben, welches in beiden Mengen vorkommt, sodass genau gesagt werden kann, ob $w$ in der Menge M oder der Menge $A^*$\ M liegt.

$$M \cap (A^*\text{ \ M}) = \empty,\text{ gilt} f(i) = g(j) = w \text{ ausgeschlossen}$$

Das Wort $w$, welches aus der Wortmenge $A^*$ stammt, und die Vereinigung der beiden Mengen, die Wortmenge ist, so muss das Wort $w$ in diesen beiden Mengen liegen. Um die Abzählbarkeit zu gewährleisten, wird abwechselnd das $i$-te-Wort aus $f$ und $g$ gesucht, sodass kein Wort vergessen wird.

$$\chi_M(w) = \begin{cases}
wahr, & \text{wenn } f(i) = w;\\
falsch, & \text{wenn } g(i) = w
\end{cases}$$

=== Teilaufgabe 3 - Illustration <tt>(Robert Rosenberger, Stefan Scheumann)</tt> ===

= Übung 4, Aufgabe 4 (Teilaufgabe 3) =

Illustrieren Sie den Beweis (Aufgabe 4.2) durch ein Scheme-Programm. 

<code id="4f8dcb1c442d7" hidden>
(define stream-car car)

(define stream-cdr
  (lambda (stm)
    (force (cdr stm))))

(define-syntax stream-cons
  (syntax-rules ()
    ((_ head tail) (cons head (delay tail)))))


  
(define stream-item
  (lambda (str k)
    (if (= k 0)
      (stream-car str)
      (stream-item (stream-cdr str) (- k 1)))))

(define stream->list
  (lambda (str n)
    (if (<= n 0)
      '()
      (cons 
        (stream-car str) 
        (stream->list (stream-cdr str) (- n 1))))))


(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-map
  (lambda (stm proc)
    (stream-cons
     (proc (string->number (stream-car stm)))
     (stream-map (stream-cdr stm) proc))))

(define natstream
  (lambda (start)
    (stream-cons (number->string start) (natstream (+ 1 start)))))

(define natzahlstream (stream-cons (number->string 0) (natstream 1)))
</code>

<code id="4f8dcae2c8d51">
; Aufzählfunktion f für alle ungerade Zahlen (hier für M)
(define f
  (lambda (n)
    (number->string (+ 1 (* n 2)))))

; Aufzählfunktion g für alle gerade Zahle (hier für A*/M)
(define g
  (lambda (n)
    (number->string (* 2 n))))

(define generiere_aufzaehlbare_menge 
  (lambda (f)
    (stream-map natzahlstream f)))

(define menge-bis print-stream)

(define M (generiere_aufzaehlbare_menge f))
(define A*-M (generiere_aufzaehlbare_menge g))

(define chi_M
  (lambda (w)
    (letrec
        ((chihelper
          (lambda (i)
            (cond
              ((string=? (f i) w) #t)
              ((string=? (g i) w) #f)
              (else
               (chihelper (+ i 1)))))))
         (chihelper 0))))
</code>

<run id="4f8dcae2c8dc4">(menge-bis M 10)</run>

<run id="4f8dcae2c8e22">(menge-bis A*-M 10) </run>

<run id="4f8dcae2c8e84">(chi_M "9199")</run>