called co-computably-enumerable or co-c.e. if its complement is computably enumerable. Equivalently, a set is co-r.e. if and only if it is at level of the arithmetical hierarchy. The complexity class of co-computably-enumerable sets is denoted co-RE. A set A is computable if and only if both A and the complement of A are computably enumerable. Some pairs of computably enumerable sets are effectively separable and some are not. Remarks According to the Church–Turing thesis, any effectively calculable function is calculable by a Turing machine, and thus a set S is computably enumerable if and only if there is some algorithm which yields an enumeration of S. This cannot be taken as a formal definition, however, because the Church–Turing thesis is an informal conjecture rather than a formal axiom. The definition of a computably enumerable set as the domain of a partial function, rather than the range of a total computable function, is common in contemporary texts. This choice is motivated by the fact that in generalized recursion theories, such as α-recursion theory, the definition corresponding to domains has been found to be more natural. Other texts use the definition in terms of enumerations, which is equivalent for computably enumerable sets. See also RE (complexity) Recursively enumerable language Arithmetical hierarchy References Rogers, H. The Theory of Recursive Functions and Effective Computability, MIT Press. ; . Soare, R. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. . Soare, Robert I. Recursively enumerable sets and degrees. Bull. Amer. Math. Soc. 84 (1978), no. 6, 1149–1181. Computability theory Theory of computation