A subset A of a set B is said to be recursively enumerable, relative to B, if there is an effective procedure that, given an element b in B, will output ‘yes’ if and only if b is an element of A. If b is not in A then, in general, the procedure will never terminate. This is a weaker notion than that of a recursive set. A set can be recursively enumerable without being recursive. The set A is also said to be semidecidable or semicomputable.

The set of Ada programs that terminates (for a given input) is recursively enumerable (with respect to the class of all Ada programs) but it is not recursive.