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:
| \(\ds k \in \operatorname{Cinstr}\) | \(\iff\) | \(\ds \operatorname{rem} \left({k, 3}\right) = 1\) | ||||||||||||
| \(\ds \) | \(\land\) | \(\ds \chi_{\operatorname{Seq} } \left({k \, \dot - \, 1}\right) = 1\) | ||||||||||||
| \(\ds \) | \(\land\) | \(\ds \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:
| \(\ds k \in \operatorname{Jinstr}\) | \(\iff\) | \(\ds \operatorname{rem} \left({k, 3}\right) = 2\) | ||||||||||||
| \(\ds \) | \(\land\) | \(\ds \chi_{\operatorname{Seq} } \left({k \, \dot - \, 2}\right) = 1\) | ||||||||||||
| \(\ds \) | \(\land\) | \(\ds \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$