Set of Codes for URM Programs is Primitive Recursive

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\operatorname{Prog}$ be the set of all code numbers of URM programs.

Then $\operatorname{Prog}$ is a primitive recursive set.


Proof

A natural number $n$ codes a URM program if and only if it codes a sequence of positive integers which are the code numbers of URM instructions.

Suppose $n$ codes such a sequence.

Then $\operatorname{len} \left({n}\right)$ is the number of terms in this sequence, where $\operatorname{len} \left({n}\right)$ is the length of $n$.

Also, for $1 \le j \le \operatorname{len} \left({n}\right)$, $\left({n}\right)_j$ is the exponent of the $j$th prime in the prime decomposition of $n$.

So $\left({n}\right)_j$ is the $j$th number in the sequence coded by $n$.

So:

$n \in \operatorname{Prog}$ if and only if $\chi_{\operatorname{Seq}} \left({n}\right) = 1$ and $\left({n}\right)_j \in \operatorname{Instr}$ for $1 \le j \le \operatorname{len} \left({n}\right)$

where $\chi_{\operatorname{Seq}}$ is the characteristic function of the set of code numbers of finite sequences of positive integers.


Now $\left({n}\right)_j \in \operatorname{Instr} \iff \chi_{\operatorname{Instr}} \left({\left({n}\right)_j}\right) = 1$.

So $\left({n}\right)_j \in \operatorname{Instr}$ for $1 \le j \le \operatorname{len} \left({n}\right)$ if and only if $\chi_{\operatorname{Instr}} \left({\left({n}\right)_j}\right) = 1$ for $1 \le j \le \operatorname{len} \left({n}\right)$.

This is the case if and only if:

$\displaystyle \prod_{j \mathop = 1}^{\operatorname{len} \left({n}\right)} = 1$

Thus $n \in \operatorname{Prog}$ if and only if:

$\displaystyle \chi_{\operatorname{Seq}} \left({n}\right) \times \prod_{j \mathop = 1}^{\operatorname{len} \left({n}\right)} = 1$


Now we define the function $g: \N^2 \to \N$ by:

$\displaystyle g \left({n, z}\right) = \begin{cases} 1 & : z = 0 \\ \displaystyle \prod_{j \mathop = 1}^z \chi_{\operatorname{Instr}} \left({\left({n}\right)_j}\right) & : \text{otherwise} \end{cases}$

We use $g$ to obtain the characteristic function of the set $\operatorname{Prog}$:

$\chi_{\operatorname{Prog}} \left({n}\right) = \chi_{\operatorname{Seq}} \left({n}\right) g \left({n, \operatorname{len} \left({n}\right)}\right)$

(We need to introduce $g$ to ensure $\chi_{\operatorname{Prog}}$ is defined if $\operatorname{len} \left({n}\right) = 0$.)


Now we have that:

So $g$ is therefore primitive recursive, as it is obtained by substitution from these.


Therefore $\chi_{\operatorname{Prog}}$ is primitive recursive as it is obtained by substitution from:


Hence $\operatorname{Prog}$ is a primitive recursive set.