BuK/IIm11/BuK-Übung04

Wiki-Quelltext dieser Seite.

== 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+1)}{2} = 13 - 10 = 3$

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

== 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>(Wer?)</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 \sqsubset M_1$ abzählbar.

=== Teilaufgabe 2 - Indirekter Beweis <tt>(Wer?)</tt> ==
zu zeigen: Nicht jede Teilmenge $M_2$ einer aufzählbaren Menge $M_1$ ist aufzählbar.
Wenn $M_1$ eine aufzählbare Menge ist, dann gilt nicht für alle Teilmengen $M_2 \sqsubset M_1$, dass sie aufzählbar sind.

== Aufgabe 3 - Beweis <tt>(Wer?)</tt> ==
Satz 3: Wenn die Menge M entscheidbar ist, dann ist M aufzählbar.

== Aufgabe 4 <tt>(Wer?)</tt> ==
Eine Menge M, mit $M \sqsubset A^*$ ist entscheidbar genau dann, wenn M und $A^*$\M aufzählbare Mengen sind.

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

=== Teilaufgabe 2 - Beweis Teil 2 <tt>(Wer?)</tt> ===
zu zeigen: Wenn M und $A^*$\M aufzählbare Mengen sind, dann ist M eine entscheidbare Menge.

=== Teilaufgabe 3 - Illustration <tt>(Wer?)</tt> ===
Illustrieren Sie den Beweis (Aufgabe 4.2) durch ein Scheme-Programm.

Bsp.: 

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

>(menge-bis M 10)
"1","3","5","7","9","11","13","15","17","19", $\ldots$
>(menge-bis a*-M 10)
"0","2","4","6","8","10","12","14","16","18", $\ldots$

>(chi_M "9199")
#t