ue4
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.