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.