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:
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:
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.
Category:URM Programs
Category:Primitive Recursive Functions