BuK-Übung04
Inhaltsverzeichnis |
Aufgabe 1
Satz 1: Eine Menge M ist genau dann aufzählbar, wenn sie semi-entscheidbar ist.
Teilaufgabe 1 (Jens Heider, Daniel Tasche, Felix Nitsche, Stefan Lüttke)
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 (Tobias Salzmann, Ronald Krause, Robert Rosenberger, Stefan Scheumann)
Ü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;
w = x + y;
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}
Außerdem gilt:
t \leq z , weil z=t+y
z= t + w - x, weil z=t+y und y=w-x
Unter Verwendung von z \leq \frac{(w+1)^{2} + (w+1)}{2} können wir w nach oben abschätzen.
Für z wird \frac{(w+1)^{2} + (w+1)}{2} eingesetzt:
\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
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 - yBeispiel: 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 = 1Aufgabe 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 (Wer?) 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 \subset M_1 abzählbar.
=== Teilaufgabe 2 - Indirekter Beweis (Wer?) 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 \subset M_1, dass sie aufzählbar sind.
Aufgabe 3 - Beweis
Satz 3: Wenn die Menge M entscheidbar ist, dann ist M aufzählbar.
Aufgabe 4
Eine Menge M, mit M \subset A^* ist entscheidbar genau dann, wenn M und A^*\M aufzählbare Mengen sind.
Teilaufgabe 1 - Beweis Teil 1
Hinrichtung des Satzes: Wenn M eine entscheidbare Menge ist, dann sind M und A^*\M aufzählbare Mengen.
Teilaufgabe 2 - Beweis Teil 2
zu zeigen: Wenn M und A^*\M aufzählbare Mengen sind, dann ist M eine entscheidbare Menge.
Teilaufgabe 3 - Illustration
Illustrieren Sie den Beweis (Aufgabe 4.2) durch ein Scheme-Programm.
Bsp.: