Recursive enumerability and the halting problem

A subset of the natural numbers is computably enumerable, abbreviated c.e., if a program can list its members, allowing repetition and arbitrary delays; the empty listing is allowed. Equivalently, membership has a semidecider that halts affirmatively exactly on members, or the set is the domain of a partial computable function. These equivalences use dovetailing when infinitely many candidate inputs or witnesses must be searched. Merely knowing that a set is countable does not give an effective listing.

Fix an effective machine numbering and a computable pairing function. The two-input halting set contains pairs whose first component describes a machine that halts on the second component. Its witnesses are bounded computation records, checked by simulating a specified finite number of steps. We also use the diagonal set K of indices e for which machine e halts on input e. Both sets are c.e.; their definitions must not be silently interchanged with the set of all total programs.

To search infinitely many computations, at stage s simulate the first s candidate computations for s steps each and report every discovered success. Repeated work is harmless; every genuinely halting candidate eventually receives enough simulation time. A more efficient scheduler may retain configurations between stages, but fairness is the essential property. Running the first computation until it halts before starting the next is not fair, because one divergent input can block all later discoveries.

If both A and its complement are c.e., decide membership by running their semideciders in alternation. Exactly one eventually accepts, because every input lies on one side. Return the corresponding Boolean answer when it does. This proves a total decision procedure, even without a uniform time bound. It also gives a useful test: an undecidable c.e. set cannot have a c.e. complement.

Suppose a total computable Hstar correctly decides whether machine e halts on input e. Construct a machine D that, on input x, loops forever if Hstar(x) says yes and halts if it says no. Because Hstar is total, D reaches the chosen branch on every input. Let d be an index of D. If Hstar(d) says yes, D(d) loops; if it says no, D(d) halts. Either answer contradicts correctness, so no such total decider exists.

The construction is about an effective enumeration containing the newly constructed program, not about a particular program literally reading its own source code. A universal simulator and ordinary program composition suffice. Since K is c.e. and undecidable, its complement is not c.e. Long unsuccessful experiments cannot refute membership uniformly. In special finite-state systems, a proved finite state bound can establish nonreachability; arbitrary Turing computations have no corresponding universal finite cutoff.