Computably enumerable set

Summary

A computably enumerable set, also called recursively enumerable or semidecidable, is a set of natural numbers whose elements can be listed by an algorithm. Equivalently, some algorithm halts exactly on the elements of the set. Every computable set is computably enumerable, but the halting set is computably enumerable and not computable. These sets are the $\Sigma^0_1$ sets of the arithmetical hierarchy and are studied through their Turing degrees.