Set of Codes for URM Instructions is Primitive Recursive

From ProofWiki
Jump to navigation Jump to search

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$