# Infinitely Many Programs for URM Computable Function

## Theorem

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

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

## Proof

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 `Jump`s 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 `Jump`s 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'$ |

...etc.

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.

$\blacksquare$

## Notes

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