Rekursiv aufzählbare Menge

Als rekursiv aufzählbare Menge (auch semi-entscheidbare Menge, positiv semi-entscheidbare Menge, halb-entscheidbare Menge, berechenbar aufzählbare Menge, kurz r.e., c.e.) wird in der Berechenbarkeitstheorie eine Menge von natürlichen Zahlen bezeichnet, wenn es einen Algorithmus gibt, der die Elemente dieser Menge aufzählt. Äquivalent ist diese Charakterisierung: Es gibt einen Algorithmus, der 1 ausgibt, wann immer die Eingabe ein Element der betreffenden Menge ist, und auf anderen Eingaben nie hält. Jede entscheidbare Menge ist rekursiv aufzählbar, aber es gibt rekursiv aufzählbare Mengen, die nicht entscheidbar sind.

Mengen von anderen Objekten als natürlichen Zahlen heißen rekursiv aufzählbar, wenn sie sich durch Gödelisierung in eine rekursiv aufzählbare Menge natürlicher Zahlen übersetzen lassen.

In der Literatur taucht gelegentlich der Begriff der berechenbaren Menge auf. Dieser Begriff wird uneinheitlich verwendet. Es können damit entscheidbare Mengen oder rekursiv aufzählbare Mengen gemeint sein.

Formale Definition

Formal werden rekursiv aufzählbare Mengen meist durch eine der folgenden, zueinander äquivalenten, Definitionen charakterisiert:

Rekursive Aufzählbarkeit

Eine Menge $M\subseteq \mathbb {N}$ heiße rekursiv aufzählbar, falls $M=\emptyset$ leer ist oder es eine totale, berechenbare Funktion $\mathbb {N} \to M$ gibt, deren Bild gerade $M$ ist.

Semi-Entscheidbarkeit

Die Menge $M$ heiße semi-entscheidbar, wenn die partielle charakteristische Funktion $\chi _{M}\colon \mathbb {N} \rightsquigarrow \{1\}$ von $M$ berechenbar ist.

Äquivalenzen zur Definition

Folgende Sätze sind untereinander äquivalent:

• $M$ ist rekursiv aufzählbar.
• $M$ ist semi-entscheidbar.
• $M$ ist vom Chomsky-Typ 0.
• $M$ ist die Menge aller Berechnungsergebnisse einer Turingmaschine.
• $M$ ist Definitionsbereich einer berechenbaren Funktion.
• $M$ ist Bildmenge einer berechenbaren Funktion.
• $M$ ist endlich oder Wertebereich einer injektiven berechenbaren Funktion.
• $M$ ist Bildmenge einer primitiv-rekursiven Funktion oder die leere Menge.
• $M$ liegt in der Klasse $\Sigma _{1}^{0}$ der arithmetischen Hierarchie.
• $M$ lässt sich many-one auf das Halteproblem reduzieren.
• Es gibt eine entscheidbare Menge $B\subseteq \mathbb {N} ^{2}$ für die gilt: $x\in M\Leftrightarrow \exists y\colon (x;y)\in B$.

Eigenschaften

• Jede entscheidbare Menge ist rekursiv aufzählbar, aber es gibt rekursiv aufzählbare Mengen, die nicht entscheidbar sind.
• Eine Menge ist genau dann entscheidbar, wenn sie und ihr Komplement rekursiv aufzählbar sind.
• Jede endliche Menge ist rekursiv aufzählbar.
• Jede rekursiv aufzählbare Menge ist abzählbar, aber nicht alle abzählbaren Mengen sind rekursiv aufzählbar.
• Jede unendliche rekursiv aufzählbare Menge besitzt Teilmengen, die nicht rekursiv aufzählbar sind.
• Der Schnitt von endlich vielen rekursiv aufzählbaren Mengen ist rekursiv aufzählbar; die Vereinigung einer rekursiv aufzählbaren Menge von rekursiv aufzählbaren Mengen ist rekursiv aufzählbar. Es gibt rekursiv aufzählbare Mengen, deren Komplement nicht rekursiv aufzählbar ist.
• Eine partielle Funktion ist genau dann berechenbar, wenn ihr Graph rekursiv aufzählbar ist.

Beispiele

• Die Menge der Paare der Form: (Programm, Eingabe) mit der Eigenschaft: das Programm hält mit der Eingabe ist rekursiv aufzählbar. Diese Menge wird auch „Universelle Sprache“ genannt. Damit ist das Halteproblem der Turingmaschinen semi-entscheidbar, denn man kann die gegebene Turingmaschine mit der gegebenen Eingabe laufen lassen und nach ihrer Terminierung 1 ausgeben. Das Komplement des Halteproblems ist nicht semi-entscheidbar.
• Die Selbstanwendbarkeit ist rekursiv aufzählbar: In obigem Beispiel beschränken wir uns auf die Eingaben, die dem jeweiligen Programm entsprechen.
• Das Äquivalenzproblem der Turingmaschinen ist nicht semi-entscheidbar. Auch das Komplement des Äquivalenzproblems ist nicht semi-entscheidbar.
• Die Werte der Busy-Beaver-Funktion sind nicht rekursiv aufzählbar.

Literatur

• Hartley Rogers: Theory of recursive functions and effective computability. McGraw-Hill, 1967.