Set of Codes for URM Programs is Primitive Recursive
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 $\map \len n$ is the number of terms in this sequence, where $\map \len n$ is the length of $n$.
Also, for $1 \le j \le \map \len n$, $\paren n_j$ is the exponent of the $j$th prime in the prime decomposition of $n$.
So $\paren n_j$ is the $j$th number in the sequence coded by $n$.
So:
- $n \in \operatorname {Prog}$ if and only if $\map {\chi_{\operatorname {Seq} } } n = 1$ and $\paren n_j \in \operatorname{Instr}$ for $1 \le j \le \map \len n$
where $\chi_{\operatorname {Seq} }$ is the characteristic function of the set of code numbers of finite sequences of positive integers.
Now $\paren n_j \in \operatorname{Instr} \iff \map {\chi_{\operatorname {Instr} } } {\paren n_j} = 1$.
So $\paren n_j \in \operatorname{Instr}$ for $1 \le j \le \map \len n$ if and only if $\map {\chi_{\operatorname {Instr} } } {\paren n_j} = 1$ for $1 \le j \le \map \len n$.
This is the case if and only if:
- $\ds \prod_{j \mathop = 1}^{\map \len n} = 1$
Thus $n \in \operatorname{Prog}$ if and only if:
- $\ds \map {\chi_{\operatorname {Seq} } } n \times \prod_{j \mathop = 1}^{\map \len n} = 1$
Now we define the function $g: \N^2 \to \N$ by:
- $\map g {n, z} = \begin{cases} 1 & : z = 0 \\ \ds \prod_{j \mathop = 1}^z \map {\chi_{\operatorname {Instr} } } {\paren n_j} & : \text {otherwise} \end{cases}$
We use $g$ to obtain the characteristic function of the set $\operatorname {Prog}$:
- $\map {\chi_{\operatorname {Prog} } } n = \map {\chi_{\operatorname {Seq} } } n \map g {n, \map \len n}$
(We need to introduce $g$ to ensure $\chi_{\operatorname{Prog}}$ is defined if $\map \len n = 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:
- the primitive recursive function $\operatorname {mult}$
- the primitive recursive function $\chi_{\operatorname {Seq} }$
- the primitive recursive function $g$
- the primitive recursive function $\len$.
Hence $\operatorname {Prog}$ is a primitive recursive set.