Unique Code for State of URM Program

Theorem

Every state of a URM program can be assigned a unique code number.

This code number is called the state code (or situation code).

Proof

The state of a URM program at a particular point in time is defined as:

the value of the instruction pointer

the value, at that point, of each of the registers that are used by the program.

Let $P$ be a URM program.

Suppose that, at a given stage of computation:

the value of the instruction pointer is $a$;

the value of register $R_k$ is $r_k$.

Let $b = \map \rho P$ be the number of registers used by $P$.

Then we can define the state code $s$ as:

$s = p_1^a p_2^{r_1} p_3^{r_2} \cdots p_{b + 1}^{r_b}$

where $p_j = \map p j$ is defined as the $j$th prime number.

Hence it follows from the Fundamental Theorem of Arithmetic that $s$ is uniquely specified for any given state.

$\blacksquare$

Comment

So, if we know the state code at a given stage of computation, we can determine the number of the instruction to be performed, and also the contents of the registers at that stage.

This is done by using the prime exponent function.

The important cases are as follows:

Let $s$ be a state code.

Then $\tuple s_1$ is the index number of the instruction about to be carried out.

If $P$ has terminated, then $\tuple s_2$ is the value held by $R_1$, which is the output.