BuK/IIm11/Studenten/sifenits/Übung04

Wiki-Quelltext dieser Seite.

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 N$

für aufzählbare Mengen gilt:

$f(x) :  N \rightarrow M$

fü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.