BuK-Übung04

Aufgabe 1

Behauptung: Eine Menge M ist genau dann aufzählbar, wenn sie semi-entscheidbar ist.

Teilaufgabe 1 (Felix Nitsche, Stefan Lüttke, Jens Heider, Daniel Tasche)

zu zeigen: Wenn M aufzählbar, dann M semi-entscheidbar.

Teilaufgabe 2 (Max Wielsch, Raik Bieniek, Ingo Körner, Christof Ochmann)

zu zeigen: Wenn M semi-entscheidbar ist, dann ist M aufzählbar.

Aufgabe 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=-\frac{p}{2}+\sqrt{\left(\frac{p}{2}\right)^2-q}
w=-\frac{1}{2}+\sqrt{\left(\frac{1}{2}\right)^2+2t}
w=-\frac{1}{2}+\sqrt{\left(\frac{1}{4}\right)^2+\frac{8t}{4}}
w=-\frac{1}{2}+\sqrt{\frac{1+8t}{4}}
w=-\frac{1}{2}+\frac{\sqrt{1+8t}}{2}
für positives w ist w = \frac{\sqrt{8t+1}-1}{2}

Außerdem gilt t \leq z = t + w - x \leq t + w \leq t + w + 1 = \frac{w^{2}+w}{2} + w + 1 = \frac{(w+1)^{2} + (w+1)}{2}

Unter verwendung von z \leq \frac{(w+1)^{2} + (w+1)}{2} können wir w nach oben abschätzen.

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

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