Computably enumerable set

In the field of computability theory, mathematicians study what can and cannot be solved by an algorithm. One important concept is the computably enumerable set, often abbreviated as c.e. or r.e. A set of natural numbers is computably enumerable if there is an algorithm that can list its members one by one. This process is also called enumeration. If the set is infinite, the algorithm will continue to run forever. However, every single member of the set will eventually appear on the list after a finite amount of time. These members do not need to appear in any specific order, such as from smallest to largest.

There are several ways to define these sets through different mathematical lenses. One way is through semidecidability. A set is semidecidable if an algorithm can confirm when a number belongs to the set. If the input number is in the set, the algorithm will eventually halt and provide an answer. However, if the number is not in the set, the algorithm might run forever without returning any information. This is why these sets are sometimes called partially decidable. In contrast, a set is considered completely decidable, or computable, if the algorithm can always tell you whether a number is in or out of the set.

Another way to view these sets is through the concept of a partial computable function. A set is computably enumerable if it is the domain of such a function. This means the function is defined only for the specific inputs that are members of the set. Alternatively, a set can be described as the range of a total computable function. This means the algorithm produces the members of the set as its output. If the set is infinite, the function can even be chosen to be injective, meaning it never repeats the same value twice. These different perspectives are mathematically equivalent.

History shows us that these ideas emerged through different mathematical paths. Diophantine sets were actually the first way to describe these groups of numbers. Diophantine sets are defined using polynomials with integer coefficients. The variables in these polynomials range over the natural numbers. A set is Diophantine if it contains exactly the non-negative numbers in the range of such a polynomial. A mathematician named Yuri Matiyasevich later proved a major connection here. He showed that every computably enumerable set is also a Diophantine set. This discovery was part of the negative solution to Hilbert's Tenth Problem.

We can find many specific examples of these sets in advanced mathematics. For instance, the set of all provable sentences in an axiomatic system is computably enumerable. There are also special categories like simple sets and creative sets. Both of these types are computably enumerable, but they are not computable. On the other hand, productive sets are a different category because they are not computably enumerable at all. We also study the complement of these sets. If the complement of a set is computably enumerable, we call that set co-computably-enumerable, or co-c.e.

Computably enumerable sets follow predictable rules when they interact with one another. If you take two c.e. sets, A and B, their intersection is also a c.e. set. This means the set of numbers found in both A and B is also listable. Similarly, the union of two c.e. sets is also computably enumerable. You can even combine them into ordered pairs using the Cantor pairing function. The resulting set will remain within the c.e. family. This stability allows mathematicians to build complex systems from simpler parts.

These concepts are deeply connected to the broader study of computational complexity and logic. In complexity theory, the class containing all computably enumerable sets is known as RE. In recursion theory, researchers study the lattice of these sets under inclusion. The Church-Turing thesis also plays a role here. It suggests that any effectively calculable function can be handled by a Turing machine. This connects the abstract idea of an algorithm to the physical reality of computation. Understanding these sets helps us define the very limits of what machines can ever know.