Halting problem

The halting set is computably enumerable but undecidable, and its complement is not computably 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$.