Eigenschaft einer Teilmenge der natürlichen Zahlen, weitestgehend synonym zum Begriff „aufzählbar“.

Eine Menge \(A\subseteq {{\mathbb{N}}}_{0}\) ist rekursiv aufzählbar, falls \(A=\varnothing \) oder falls es eine total berechenbare Funktion \(f:{{\mathbb{N}}}_{0}\to {{\mathbb{N}}}_{0}\) gibt, so daß A die Wertemenge von f ist, also \begin{eqnarray}A=\{f(0),f(1),f(2),\ldots\}.\end{eqnarray} Man sagt dann, f zählt die Menge A auf.

Der Begriff „rekursiv aufzählbar“ unterscheidet sich von „abzählbar“ dadurch, daß die Berechenbarkeit der Funktion f verlangt wird. Insbesondere braucht eine Teilmenge einer rekursiv aufzählbaren Menge nicht notwendig selbst rekursiv aufzählbar zu sein.

Es gilt der Satz, daß eine Menge genau dann rekursiv aufzählbar ist, wenn sie semi-entscheidbar ist. Hieraus ergibt sich weiterhin, daß eine Menge genau dann entscheidbar ist (Entscheidbarkeit), wenn die Menge und ihre Komplementmenge rekursiv aufzählbar sind.