Computable reduction by staged enumeration (source code)

= Computable reduction by staged enumeration

A <many-one reduction> can compile a source instance into a program whose <domain of a function> changes according to the successive finite stages of a simulation. The compiler must be a <total computable function>; the compiled program may diverge.

For example, let $K=\{e:\varphi_e(e)\mathbin\downarrow\}$ be the <diagonal halting set>. Compile $e$ into a program $M_e$ that, on input $x\in\mathbb N$, uses a <bounded simulation of a computation> to test whether $\varphi_e(e)$ halts within $x$ steps. If no halt is seen, return zero; if a halt is seen, loop forever. The <S-m-n theorem> gives a <total computable function> $g$ producing the index of $M_e$. Consequently
$$
\operatorname{dom}(\varphi_{g(e)})=\begin{cases}\mathbb N,&e\notin K,\\ \{x:\text{the halt is not seen within }x\text{ steps}\},&e\in K.\end{cases}
$$
The second <set> is a finite initial segment. Therefore $e\notin K$ if and only if $g(e)$ belongs to the <infinite-domain index set>. This proves $\overline K\leq_m\mathbf{Inf}$, and hence $\mathbf{Inf}$ is not <computably enumerable>: preimages of <computably enumerable sets> under <total computable functions> are <computably enumerable>, whereas $\overline K$ is not. The construction detects halting by finite evidence and never attempts to decide nonhalting.