BuK-Kreativaufgabe04 G2

Aus ProgrammingWiki
< BuK < IIm10
Archivierte Version vom 2011-04-18T17:18:22+00:00. Aktuelle Version

Zeitbeschränkte Prozesse mit Engines

Folgender Satz soll auf dieser Seite mittels Scheme-Engines dargestellt werden:

Wenn M semi-entscheidbar ist, dann ist M aufzählbar.

Aus M ist semi-entscheidbar kann man folgenden Schluss ziehen:

Es existiert eine Funktion

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

Die Funktion ist partiell berechenbar, d.h. es gibt Eingabeparameter für die \chi_M ' stoppt, und welche für die die Funktion nicht stoppt.