Unique Code for URM Program
Theorem
Any URM program can be assigned a unique code number.
Proof
Let $\mathbf P$ be the set of all URM programs.
Let $P \in \mathbf P$ be a URM program with $k$ basic instructions:
Line | Command | ||
---|---|---|---|
$1$ | $I_1$ | ||
$2$ | $I_2$ | ||
$\vdots$ | $\vdots$ | ||
$k$ | $I_k$ |
We define the mapping $\gamma: \mathbf P \to \N$ as follows:
- $\ds \map \gamma P = \prod_{i \mathop = 1}^k p_i^{\map \beta {I_i} }$
where:
- $p_i$ is the $i$th prime number;
- $\map \beta {I_i}$ is the unique code for instruction $i$.
Hence it follows from the Fundamental Theorem of Arithmetic that $\gamma$ is uniquely specified for any given URM program.
Thus $\gamma$ is an injection.
$\blacksquare$
For a given $P$, the number $\map \gamma P$ is referred to as the code number of $P$.
Does Not Code
Not every $e \in \N$ is the code number of a URM program.
If $e$ is not the code of any URM program, we say that $e$ does not code a URM program.
Note
The coding scheme for $\mathbf P$ is not unique.
This particular scheme lends itself especially to number-theoretical analysis techniques.