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.
Articles by others on the same topic
There are currently no matching articles.