You are here
Homeexamples of primitive recursive encoding
Primary tabs
examples of primitive recursive encoding
In this entry, we present three examples of primitive recursive encodings. In all the examples, the following notations are used: $\mathbb{N}$ is the set of all natural numbers (including $0$), $\mathbb{N}^{*}$ is the set of all finite sequences over $\mathbb{N}$, and $E:\mathbb{N}^{*}\to\mathbb{N}$ is the encoding in question. For any sequence $a_{1},\ldots,a_{k}$, its image under $E$ is denoted by $\langle a_{1},\ldots,a_{k}\rangle$, and is called the sequence number corresponding to $a_{1},\ldots,a_{k}$. Furthermore, $()$ denotes the empty sequence, and its sequence number is denoted by $\langle\rangle$. The fact that the $E$ in each of the examples below is in fact encoding is proved in this entry.
Example 1. (Multiplicative encoding) $E$ is defined as follows:
$\displaystyle\langle\rangle$  $\displaystyle:=$  $\displaystyle 1,$  
$\displaystyle\langle a_{1},\ldots,a_{k}\rangle$  $\displaystyle:=$  $\displaystyle p_{1}^{{s(a_{1})}}\cdots p_{k}^{{s(a_{k})}},$ 
where $s$ is the successor function, and $p_{1},\ldots,p_{k}$ are the first $k$ prime numbers.
To see that $E$ is primitive recursive, we verify the following:

the predicate “$x$ is a sequence number” is primitive recursive: a number $x\in\mathbb{N}$ is a sequence number iff $x=1$ or, if $px$ for some prime $p$, then $qx$ for any prime $q\leq p$. The predicates
$\Phi_{1}:=``px\mbox{ for some prime }p\mbox{''}\equiv``\exists p\leq x(P(p)% \wedge(px))\mbox{''},$ $\Phi_{2}:=``p\mbox{ is prime and }qx\mbox{ for all primes }q\leq p\mbox{''}% \equiv``\forall q\leq p(P(p)\wedge P(q)\wedge(qx))\mbox{''}$ where $P(r):=$ “$r$ is prime”, are primitive recursive by bounded quantification. Thus “$x$ is a sequence number” iff “$x=1$ or $\Phi_{1}\rightarrow\Phi_{2}$” iff “$(x=1)\vee(\neg\Phi_{1}\vee\Phi_{2})$”, is primitive recursive as a result.

$E_{k}(a_{1},\ldots,a_{k}):=p_{1}^{{s(a_{1})}}\cdots p_{k}^{{s(a_{k})}}$ is clearly primitive recursive.

$\operatorname{lh}(x)$ can be defined as the number of primes dividing $x$, which is primitive recursive.
Example 2. (Encoding via a pairing function) First, let $J:\mathbb{N}^{2}\to\mathbb{N}$ be a (primitive recursive) pairing function. For any $n\geq 2$, define
$\displaystyle J_{2}(x_{1},x_{2})$  $\displaystyle:=$  $\displaystyle J(x_{1},x_{2})$  
$\displaystyle J_{{n+1}}(x_{1},\ldots,x_{n},x_{{n+1}})$  $\displaystyle:=$  $\displaystyle J(x_{1},J_{n}(x_{2},\ldots,x_{{n+1}})).$ 
Then define $E$ by
$\displaystyle\langle\rangle$  $\displaystyle:=$  $\displaystyle 0,$  
$\displaystyle\langle a_{1},\ldots,a_{k}\rangle$  $\displaystyle:=$  $\displaystyle J(k,J_{k}(a_{1},\ldots,a_{k})).$ 
$E$ is primitive recursive because

$E$ is a bijection, so the predicate “$x$ is a sequence number” is the same as “$x\in\mathbb{N}$”, which is clearly primitive recursive,

$E_{k}(a_{1},\ldots,a_{k}):=J(k,J_{k}(a_{1},\ldots,a_{k}))$ is primitive recursive since both $J$ and $J_{k}$ are, the latter of which can be shown to be primitive recursive by induction,

The two functions $R,L:\mathbb{N}\to\mathbb{N}$ such that $J(L(m),R(m))=m$ are primitive recursive. So $\operatorname{lh}(x)=L(x)$ in particular is primitive recursive.

If $J_{k}(a_{1},\ldots,a_{k})=b$, then $a_{1}=L(b),a_{2}=LRL(b),\ldots,a_{{k1}}=(LR)^{{k2}}L(b)$, and $a_{k}=R(LR)^{{k2}}L(b)$. Thus,
$(x)_{y}=\left\{\begin{array}[]{ll}(LR)^{y}(x)&\textrm{if }y<L(x),\\ R(LR)^{y}(x)&\textrm{if }y=L(x),\\ 0&\textrm{otherwise}.\end{array}\right.$ is primitive recursive, since each case is primitive recursive.
Example 3. (Digital Representation) Pick a positive integers $p>1$. Define $E$ by
$\displaystyle\langle\rangle$  $\displaystyle:=$  $\displaystyle 1$  
$\displaystyle\langle a\rangle$  $\displaystyle:=$  $\displaystyle p^{{s(a)}}$  
$\displaystyle\langle a_{1},\ldots,a_{k},a_{{k+1}}\rangle$  $\displaystyle:=$  $\displaystyle\langle a_{1}\rangle(\langle a_{2},\ldots,a_{{k+1}}\rangle+1).$ 
In other words,
$\langle a_{1},\ldots,a_{k}\rangle=p^{{s(a_{1})}}+p^{{s(a_{1})+s(a_{2})}}+% \cdots p^{{s(a_{1})+\cdots+s(a_{k})}}.$  (1) 
To see that $E$ is primitive recursive, we first define three functions $f:\mathbb{N}\to\mathbb{N}$ given by $f(x):=\operatorname{lo}(p,x)$, the exponent of $p$ in $x$, $g:\mathbb{N}\to\mathbb{N}$ given by $g(x):=\operatorname{quo}(x,p^{{f(x)}})\dot{}1$, and $h:\mathbb{N}^{2}\to\mathbb{N}$ given by
$\displaystyle h(x,0)$  $\displaystyle:=$  $\displaystyle x$  
$\displaystyle h(x,n+1)$  $\displaystyle:=$  $\displaystyle g(h(x,n)).$ 
Clearly, $f,g,h$ are all primitive recursive. Furthermore, $h$ has the property that if $h(x,n)>0$, then $h(x,n+1)<h(x,n)$, and therefore $h(x,n)=0$ for large enough $n$. Using $h$, we may proceed to show that $E$ is primitive recursive:

the predicate “$x$ is a sequence number” is equivalent to the predicate
“$(x=1)\vee((x>0)\wedge(\forall n\;ph(x,n)))$”
which is equivalent to the predicate
“$(x=1)\vee((x>0)\wedge(\forall n\leq x\;ph(x,n)))$”
since $p>1$. As the quantification is bounded, the predicate is primitive recursive.

$E_{k}(a_{1},\ldots,a_{k})=\langle a_{1},\ldots,a_{k}\rangle$ is primitive recursive by equation (1) above.

$\operatorname{lh}(x)$ can be defined as the number of $n$ such that $h(x,n)\neq 0$, or
$\sum_{{i=0}}^{x}\operatorname{sgn}(h(x,i)),$ which is primitive recursive, because it is a bounded sum.

If $\langle a_{1},\ldots,a_{k}\rangle=x$, then $f(h(x,0))=s(a_{1}),\ldots,f(h(x,k1))=s(a_{k})$. Therefore, $(x)_{y}$ is just $f(h(x,y\dot{}1))\dot{}1$, which is primitive recursive.
Remark. In the third example, $E$ can be more generally defined so that
$\langle a_{1},\ldots,a_{k},a_{{k+1}}\rangle:=\langle a_{1}\rangle(r\langle a_{% 2},\ldots,a_{{k+1}}\rangle+q),$ 
provided that $p,q$ are coprime. It is fairly straightforward to show that $E$ is again primitive recursive.
Mathematics Subject Classification
94A60 no label found68Q45 no label found68Q05 no label found03D20 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections