BuK-Kreativaufgabe04 G1

Aus ProgrammingWiki
< BuK < IIm10
Archivierte Version vom 2011-04-14T13:57:56+00:00. Aktuelle Version

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:

  1. M ist semi-entscheidbar
  2. M ist aufzählbar

Für die Semi-Entscheidbarkeit gilt:

\chi ':A^*\rightarrow M \chi_M '(w)=\begin{cases} true, \text{wenn }w \in M \\ n.d., sonst \end{cases}

Diese Funktion ist partiell berechenbar.

Für die Aufzählbarkeit gilt:

f: \mathbb{N}_0\rightarrow M

Diese Funktion ist total, surjektiv und berechenbar.

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

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

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

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