Padding lemma (source code)

= Padding lemma

For a standard effective numbering $e\mapsto\varphi_e$ of <partial computable functions>, there is a <total computable function> $p(e,k)$, injective in the pair $(e,k)$, such that $\varphi_{p(e,k)}=\varphi_e$. Thus infinitely many different <program indices> can describe exactly the same computation. The uniformity matters: the extra index can be chosen algorithmically, rather than merely known to exist.

For a concrete <Turing machine> coding, insert an unreachable block carrying the original description and the integer $k$, with a recognizable delimiter. Execution never enters that block, so the <partial computable function> remains unchanged; the recognizable description makes the padded indices distinct. The general version for acceptable numberings transfers this construction through a computable isomorphism of numberings. Padding distinguishes properties of <program indices> from properties of the <partial computable functions> they compute.