BuK/IIm10/BuK-Kreativaufgabe04 G1

Wiki-Quelltext dieser Seite.

=Zeitbeschränkte Prozesse mit Engines=
; Satz
: Wenn M semi-entscheidbar ist, dann ist M aufzählbar.

Beim Analysieren des Satzes erkennt man, dass folgendes gelten soll:
# M ist semi-entscheidbar
# M ist aufzählbar

Für die Semi-Entscheidbarkeit gilt:

<math>
\chi ':A^*\rightarrow M
</math>

<math>
\chi_M '(w)=\begin{cases}
true, \text{wenn }w \in M \\
n.d., sonst
\end{cases}
</math>

Diese Funktion ist partiell '''berechenbar'''.

Für die Aufzählbarkeit gilt:

<math>
f: \mathbb{N}_0\rightarrow M
</math>

Diese Funktion ist total, surjektiv und '''berechenbar'''.

Des Weiteren gilt, dass <math>A^*</math> aufzählbar unendlich ist. Das bedeutet, das eine Funktion <math>g: \mathbb{N}_0 \rightarrow A^*</math> surjektiv und berechenbar ist.

Die Funktion um den Satz zu beweisen würde wie folgt aufgebaut sein:

<math>
f(i)=\begin{cases}
g(i),\text{wenn } \chi_M '(g(i))\\
a \in M, \text{sonst}
\end{cases}
</math>

Leider kann die Funktion so nicht berechnet werden, da eine Überprüfung von <math>g(i)</math> mit <math>\chi '</math> nicht zu einem Ende kommt, wenn <math>g(i)</math> nicht in <math>M</math> enthalten ist.