Shoenfield's limit lemma

Use the halting-set meaning of $0^{\mathrm{\prime }}$ fixed in Post's theorem. A query code $e$ specifies an ordinary computation whose halting is in question. Put $0_s^{\mathrm{\prime }}=\{e\le s:\text{the computation coded by }e\text{ halts within }s\text{ steps}\}$. Bounded simulation makes membership in $0_s^{\mathrm{\prime }}$ uniformly decidable in $(e,s)$. These sets are finite and increasing, and their union is $0^{\mathrm{\prime }}$: a genuinely halting computation enters once $s$ exceeds both its code and its halting time; a nonhalting computation never enters.

If $A{\le }_T{0}^{\mathrm{\prime }}$, fix $M^{0^{\mathrm{\prime }}}$ computing ${\chi }_A$. Define $g(x,s)$ by simulating at most $s$ oracle-machine transitions of $M(x)$, answering each query by the decidable set $0_s^{\mathrm{\prime }}$. Return the output if it halts with output in $\{0,1\}$ within the cutoff, and return $0$ otherwise. Each stage halts, so $g$ is total computable and bit-valued even when an incorrect oracle sends $M$ into a loop or an unintended output. No time-efficiency bound on this finite simulation is asserted.

For fixed $x$, the true run has a finite transition length $r$ and a finite query set $F$ by L1. All negative answers on $F$ are correct at every stage. Each positive answer becomes permanently correct by step 1.1; take $s_0\ge r$ beyond the finitely many corresponding entry stages. For every $s\ge s_0$, L1 gives exactly the true run with oracle $0_s^{\mathrm{\prime }}$, and the cutoff does not interrupt it. Thus $g(x,s)={\chi }_A(x)$ eventually. An empty $F$ requires only the time cutoff, and $s_0$ is an existence bound, not a claimed computable modulus.

Conversely, let total computable $h(x,s)$ converge eventually to ${\chi }_A(x)$. For each $(x,s)$, effectively form the ordinary program that computes $h(x,s)$, searches $t=s+1,s+2,\dots$, and halts upon finding $h(x,t)\mathrm{\ne }h(x,s)$. Its halting is a $0^{\mathrm{\prime }}$ question. Ask these questions for $s=0,1,\dots$ until receiving a negative answer. Eventual constancy ensures termination; a negative answer means that all later values equal the current value, which must therefore be ${\chi }_A(x)$. Output it. This computes $A$ in $0^{\mathrm{\prime }}$ and proves the reverse implication.