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:

$\ds \map \gamma P = \prod_{i \mathop = 1}^k p_i^{\map \beta {I_i} }$

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 $\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.