# Unique Code for URM Instruction

## Theorem

Each basic instruction $I$ in a URM Program can be identified with a unique code number $\beta \left({I}\right)$.

We also define the following sets:

• $\operatorname{Zinstr}$ is the set of codes of all the Zero instructions
• $\operatorname{Sinstr}$ is the set of codes of all the Successor instructions
• $\operatorname{Cinstr}$ is the set of codes of all the Copy instructions
• $\operatorname{Jinstr}$ is the set of codes of all the Jump instructions.

Then we define $\operatorname{Instr}$ to be the set of codes of all basic URM instructions.

That is:

$\operatorname{Instr} = \operatorname{Zinstr} \cup \operatorname{Sinstr} \cup \operatorname{Cinstr} \cup \operatorname{Jinstr}$.

## Proof

Each basic URM instruction is of one of the following forms:

 Zero $Z \left({n}\right)$ Successor $S \left({n}\right)$ Copy $C \left({m, n}\right)$ Jump $J \left({m, n, q}\right)$

Let $\Bbb I$ be the set of all basic URM instructions.

We define the mapping $\beta: \Bbb I \to \N$ as follows:

• $\beta \left({Z \left({n}\right)}\right) = 6 n - 3$
• $\beta \left({S \left({n}\right)}\right) = 6 n$
• $\beta \left({C \left({m, n}\right)}\right) = 2^m 3^n + 1$
• $\beta \left({J \left({m, n, q}\right)}\right) = 2^m 3^n 5^q + 2$

We note that:

• $\beta \left({Z \left({n}\right)}\right) \equiv 3 \pmod 6$
• $\beta \left({S \left({n}\right)}\right) \equiv 0 \pmod 6$
• $\beta \left({C \left({m, n}\right)}\right) \equiv 1 \pmod 3$
• $\beta \left({J \left({m, n, q}\right)}\right) \equiv 2 \pmod 3$

So, if $\beta \left({I_1}\right) = \beta \left({I_2}\right)$, then both instructions must be of the same type.

Hence it follows from the Fundamental Theorem of Arithmetic that $\beta$ is uniquely specified for any given basic URM instruction.

Thus $\beta$ is an injection.

$\blacksquare$

## Note

The coding scheme for $\Bbb I$ (i.e., the mapping $\beta$) is not unique.

This particular scheme lends itself especially to number-theoretical analysis techniques.