Unique Code for URM Program

From ProofWiki
Jump to navigation Jump to search

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:

$\displaystyle \gamma \left({P}\right) = \prod_{i=1}^k p_i^{\beta \left({I_i}\right)}$

where:

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 $\gamma \left({P}\right)$ 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.