Padding lemma Created 2026-09-24 Updated 2026-11-05
For a standard effective numbering of partial computable functions, there is a total computable function , injective in the pair , such that . 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 , 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.