Infinitely Many Programs for URM Computable Function

From ProofWiki
Jump to navigation Jump to search


Let $g: \N^k \to \N$ be a URM computable function.

Then there is an infinite number of URM programs which compute $g$.


As $g$ is URM computable, there exists a URM program which computes it.

Let $Q$ be such a program.

Let $n \in \N$.

Increment the Jumps in $Q$ by $n$ lines[1]. Call this amended version $Q'$.

This is because, as $Q$ was written so as to start from line 1, we need to move all the Jumps so as to point to the same lines relative to the start of $Q'$.

Then we can build the following URM program:

Line Command
$1$ $C \left({1, 1}\right)$
$2$ $C \left({1, 1}\right)$
$\vdots$ $\vdots$
$n$ $C \left({1, 1}\right)$
$n + 1$ The start of $Q'$


Each of the $C \left({1, 1}\right)$ instructions codes the identity function.

So adding it to the front of $Q$ has no effect on the behaviour of $Q$

It is clear that for each $n \in \N$ there is a different URM program which computes $f$.

The result follows from Infinite if Injection from Natural Numbers.



  1. To increment the Jumps by $r$ for any normalized URM program is done by changing all Jumps of the form $J \left({m, n, q}\right)$ to $J \left({m, n, q+r}\right)$.