Recursively enumerable language

A language is computably enumerable when a machine recognizes its members, possibly running forever on nonmembers.

A formal language whose complement of a set, relative to the set of all input words, is a recursively enumerable language. A recognizer for the complement detects every negative instance eventually and need not halt on positive instances. A formal language is a decidable language exactly when it and its complement are both recursively enumerable languages.

The halting problem asks, given a program and an input, whether running that program on that input eventually stops. It is undecidable: no total algorithm answers correctly for every encoded program and input.

If a decider $H(P,x)$ existed, construct a program $D(P)$ that loops when $H(P,P)$ predicts halting and stops when it predicts nonhalting. Running $D$ on its own description contradicts either prediction. Halting instances are nevertheless computably enumerable, since finite simulations eventually witness any halt. If nonhalting instances were also computably enumerable, dovetailing the two recognizers would decide the problem, so their complement is not enumerable.

A machine's halting times admit a total computable function as a bound on all inputs in its domain if and only if that domain is a computable set. A bound decides the domain by finite simulation; conversely, a domain decider allows returning zero outside the domain and the exactly simulated halting time inside it. In particular every machine computing a total computable function has an exact computable running-time function, while nontotal machines may or may not have total bounds.

The halting set of a Turing machine $T$ is the set of inputs on which it eventually halts. For a deterministic machine with a designated terminal state, eventual halting is invariant along every transition edge, even when that edge is traversed backwards. This observation justifies passing from forward computations to symmetric equality derivations in a semigroup presentation.

For an effective enumeration of unary partial computable functions, the diagonal halting set isEquivalently, for an enumeration $W_e$ of computably enumerable sets, $K=\{e:e\in W_e\}$.

Every recursively enumerable set many-one reduces to the diagonal halting set. If a program halts exactly on $X$, the S-m-n theorem produces from $x$ an index $g(x)$ for a unary program that ignores its input and performs that computation on $x$. ThenConversely, a computable preimage of a recursively enumerable set is recursively enumerable.

If $0\notin K$, thendiffers from $K$, while the computable map $n\mapsto 2n+1$ proves $K{\le }_{m}S$.

The set $S$ is also a computably enumerable set, so the many-one completeness of the halting problem gives $S{\le }_{m}K$. Together the two many-one reductions place $S$ and $K$ in the same many-one degree.