Der Begriff der semi-entscheidbaren Menge (auch halb-entscheidbar genannt) kommt aus der Theorie der Berechenbarkeit oft auch Rekursionstheorie genannt. Diese Theorie ist ein Teilgebiet der Theoretischen Informatik. Die Theorie der Berechenbarkeit arbeitet mit einem Begriff des Rechnens. Dieser Begriff wurde vielfältig formalisiert, z. B. mit Turingmaschinen, rekursive Funktionsdefinitionen und anderen.

Zum Hintergrund siehe die ausführliche Darstellung unter Berechenbarkeit.

Definition

---

Eine Menge $A$ heißt genau dann semi-entscheidbar, wenn es eine partiell berechenbare Funktion $f:A\backslash to\; \backslash mathbb\; B$ gibt mit $f(x)\; =\; \backslash top\; \backslash iff\; x\backslash in\; A$.
Hintergrund: Wenn eine Ausgabe $\backslash top$ geliefert wird, ist eine positive Antwort eingetroffen; wenn diese Ausgabe nicht gekommen ist, müssen wir noch warten oder sie kommt nie. In der Regel können wir das Komplement einer semi-entscheidbaren Menge nicht semi-entscheiden.

Zur Verwendung des Begriffs Berechenbare Menge

---

In der Literatur taucht gelegentlich der Begriff der berechenbaren Menge auf. Dieser Begriff wird uneinheitlich benutzt: So gibt es hier eine Definition, die in obiger Definition verlangt, dass $f$ total und berechenbar sein soll. Eine andere sieht vor, dass $f$ nur partiell berechenbar sein muss. Im ersten Fall definieren wir damit den Begriff rekursiv entscheidbare Menge im zweiten Fall semi-entscheidbare Menge.

Eigenschaften der semi-entscheidbaren Mengen

---

• Eine Menge ist semi-entscheidbar genau dann, wenn sie rekursiv aufzählbar ist.
• Eine Menge ist rekursiv entscheidbar genau dann, wenn sie und ihr Komplement semi-entscheidbar sind.
• Wenn eine Abbildung total berechenbar ist, dann ist ihr Wertebereich semi-entscheidbar.

Theoretische Informatik | Rekursionstheorie