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.