BuK/IIm11/Studenten/sidatasc/ue4

Wiki-Quelltext dieser Seite.

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

=== Teilaufgabe 1 ===
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 ===
zu zeigen: Wenn M semi-entscheidbar ist, dann ist M aufzählbar.