rekursiv aufzählbar

Eine Sprache $A \subseteq Σ^{*}$ heißt rekursiv aufzählbar, falls $A = \emptyset$ gilt oder falls es eine totale, berechenbare Funktion

f : N \to Σ^{*}

derart gibt, dass

A = f (0), f (1), f (2), \dots = f (N) .

„ $\sim f$ zählt $A$ auf.“