Übung04
Behauptung: Eine Menge M ist genau dann aufzählbar, wenn sie semi-entscheidbar ist. [Bearbeiten] Teilaufgabe 1 (Felix Nitsche, Stefan Lüttke, Jens Heider, Daniel Tasche) zu zeigen: Wenn M aufzählbar, dann M semi-entscheidbar.
Annahme:
M \subseteq X x, n \in Nfür aufzählbare Mengen gilt:
f(x) : N \rightarrow Mfür semi-entscheidbare Mengen gilt:
$ g(n \in X) = \begin{cases} wahr; & \text{wenn } n \in M;\\ \bot; & sonst \end{cases} $
Es kann nun bewiesen werden dass eine aufzählbare Menge immer auch semi-entscheidbar ist, wenn man einen Algorithmus angibt, der mithilfe der Funktion f(x) die Funktion g(n) nachbildet. Dies kann erreicht werden, indem die Funktion f(x) in einer Schleife nacheinander mit jedem Element aus X aufgerufen wird. Ist das Ergebnis dabei gleich n wird wahr zurückgegeben. Ist nun n \in M gibt der Algorithmus wahr zurück, andernfalls terminiert er nicht.