Unique Code for URM Instruction

From ProofWiki
Jump to navigation Jump to search

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.