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 $\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:

$\paren n_j$ is primitive recursive;
$\operatorname {Instr}$ is primitive recursive.

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.