Das Kefk Network Wiki befindet sich im Testbetrieb.

---

Aus Kefk.

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 gibt mit .
Häufig wird die Semi-Entscheidbarkeit auch als Aufzählbarkeit bezeichnet. Hintergrund: Wenn eine Ausgabe 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 genau dann semi-entscheidbar, wenn sie rekursiv aufzählbar ist.
• Eine Menge ist genau dann entscheidbar, wenn sie und ihr Komplement semi-entscheidbar sind.
• Wenn eine Abbildung total berechenbar ist, dann ist ihr Wertebereich semi-entscheidbar.

Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Semi-entscheidbare_Menge, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation.