rekursive Aufzählbarkeit

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 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.