# Set of Codes for URM Instructions is Primitive Recursive

## Theorem

The set $\operatorname{Instr}$ of codes of all basic URM instructions is primitive recursive.

## Proof

Since the Union of Primitive Recursive Sets is itself primitive recursive, all we need to do is show that each of $\operatorname{Zinstr}$, $\operatorname{Sinstr}$, $\operatorname{Cinstr}$ and $\operatorname{Jinstr}$ are primitive recursive.

First we consider $\operatorname{Zinstr}$.

$\operatorname{Zinstr} = \left\{{\beta \left({Z \left({n}\right)}\right): n \in \N^*}\right\} = \left\{{6 n - 3: n \in \N^*}\right\}$.

So $\operatorname{Zinstr}$ is the set of natural numbers which are divisible by $3$ but not $6$.

Thus its characteristic function is given by:

$\chi_{\operatorname{Zinstr}} \left({k}\right) = \operatorname{div} \left({k, 3}\right) \times \overline{\operatorname{sgn}}\left({\operatorname{div} \left({k, 6}\right)}\right)$

where:

$\operatorname{div}$ is primitive recursive
$\overline{\operatorname{sgn}}$ is primitive recursive
Multiplication is Primitive Recursive
$3$ and $6$ are constants

Hence $\operatorname{Zinstr}$ is primitive recursive.

Next we consider $\operatorname{Sinstr}$.

$\operatorname{Sinstr} = \left\{{\beta \left({S \left({n}\right)}\right): n \in \N^*}\right\} = \left\{{6 n: n \in \N^*}\right\}$.

So $\operatorname{Sinstr}$ is the set of natural numbers which are divisible by $6$.

Thus its characteristic function is given by:

$\chi_{\operatorname{Sinstr}} \left({k}\right) = \operatorname{sgn} \left({k}\right) \times \operatorname{div} \left({k, 6}\right)$

where:

$\operatorname{div}$ is primitive recursive
$\operatorname{sgn}$ is primitive recursive
Multiplication is Primitive Recursive
$6$ is constant

Hence $\operatorname{Sinstr}$ is primitive recursive.

Next we consider $\operatorname{Cinstr}$.

We have that $\beta \left({C \left({n, m}\right)}\right) = 2^m 3^n + 1$.

Hence $k \in \operatorname{Cinstr}$ iff $k \equiv 1 \pmod 3$ and $k - 1$ codes a pair of positive integers.

That is:

 $\displaystyle k \in \operatorname{Cinstr}$ $\iff$ $\displaystyle \operatorname{rem} \left({k, 3}\right) = 1$ $\displaystyle$ $\land$ $\displaystyle \chi_{\operatorname{Seq} } \left({k \, \dot - \, 1}\right) = 1$ $\displaystyle$ $\land$ $\displaystyle \operatorname{len} \left({k \, \dot - \, 1}\right) = 2$

We can introduce two properties:

$P \left({k}\right) \iff \operatorname{eq} \left({\operatorname{rem} \left({k, 3}\right), 1}\right)$
$Q \left({k}\right) \iff \operatorname{eq} \left({\operatorname{len} \left({k \, \dot - \, 1}\right), 2}\right)$

$\chi_{P}$ is primitive recursive since it is obtained by substitution from:

$\operatorname{eq}$ is primitive recursive
$\operatorname{rem}$ is primitive recursive
$3$ and $1$ are constants

$\chi_{Q}$ is primitive recursive since it is obtained by substitution from:

$\operatorname{eq}$ is primitive recursive
$\operatorname{len}$ is primitive recursive
$k \, \dot - \, 1$ is primitive recursive
$2$ and $1$ are constants

Thus the characteristic function of $\operatorname{Cinstr}$ is given by:

$\chi_{\operatorname{Cinstr}} = \chi_{P} \left({k}\right) \chi_{Q} \left({k}\right) \chi_{\operatorname{Seq}} \left({k \, \dot - \, 1}\right)$

where:

$\chi_{P}$ is primitive recursive
$\chi_{Q}$ is primitive recursive
Multiplication is Primitive Recursive
$\chi_{\operatorname{Seq}}$ is primitive recursive
$k \, \dot - \, 1$ is primitive recursive
$1$ is constant

Hence $\operatorname{Cinstr}$ is primitive recursive.

Finally we consider $\operatorname{Jinstr}$.

We have that $\beta \left({J \left({n, m, q}\right)}\right) = 2^m 3^n 5^n + 2$.

Hence $k \in \operatorname{Jinstr}$ iff $k \equiv 2 \pmod 3$ and $k - 1$ codes a triad of positive integers.

That is:

 $\displaystyle k \in \operatorname{Jinstr}$ $\iff$ $\displaystyle \operatorname{rem} \left({k, 3}\right) = 2$ $\displaystyle$ $\land$ $\displaystyle \chi_{\operatorname{Seq} } \left({k \, \dot - \, 2}\right) = 1$ $\displaystyle$ $\land$ $\displaystyle \operatorname{len} \left({k \, \dot - \, 2}\right) = 3$

We can introduce two properties:

$R \left({k}\right) \iff \operatorname{eq} \left({\operatorname{rem} \left({k, 3}\right), 2}\right)$
$S \left({k}\right) \iff \operatorname{eq} \left({\operatorname{len} \left({k \, \dot - \, 2}\right), 3}\right)$

$\chi_R$ is primitive recursive since it is obtained by substitution from:

$\operatorname{eq}$ is primitive recursive
$\operatorname{rem}$ is primitive recursive
$3$ and $2$ are constants

$\chi_S$ is primitive recursive since it is obtained by substitution from:

$\operatorname{eq}$ is primitive recursive
$\operatorname{len}$ is primitive recursive
$k \, \dot - \, 2$ is primitive recursive
$2$ and $3$ are constants

Thus the characteristic function of $\operatorname{Jinstr}$ is given by:

$\chi_{\operatorname{Jinstr}} = \chi_R \left({k}\right) \chi_S \left({k}\right) \chi_{\operatorname{Seq}} \left({k \, \dot - \, 2}\right)$

where:

$\chi_R$ is primitive recursive
$\chi_S$ is primitive recursive
Multiplication is Primitive Recursive
$\chi_{\operatorname{Seq}}$ is primitive recursive
$k \, \dot - \, 2$ is primitive recursive
$2$ is constant

Hence $\operatorname{Jinstr}$ is primitive recursive.

The result follows.

$\blacksquare$