# 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 (http://planetmath.org/EncodingWords).

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 $p|x$ for some prime $p$, then $q|x$ for any prime $q\leq p$. The predicates

 $\Phi_{1}:=p|x\mbox{ for some prime }p\mbox{''}\equiv\exists p\leq x(P(p)% \wedge(p|x))\mbox{''},$
 $\Phi_{2}:=p\mbox{ is prime and }q|x\mbox{ for all primes }q\leq p\mbox{''}% \equiv\forall q\leq p(P(p)\wedge P(q)\wedge(q|x))\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.

• $(x)_{y}$ can be defined as the exponent of the $y$-th prime in $x$ (the largest power of $p_{y}$ dividing $x$), which is again 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_{k-1}=(LR)^{k-2}L(b)$, and $a_{k}=R(LR)^{k-2}L(b)$. Thus,

 $(x)_{y}=\left\{\begin{array}[]{ll}(LR)^{y}(x)&\textrm{if }y

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), 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\;p|h(x,n)))$

which is equivalent to the predicate

$(x=1)\vee((x>0)\wedge(\forall n\leq x\;p|h(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,k-1))=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.

Title examples of primitive recursive encoding ExamplesOfPrimitiveRecursiveEncoding 2013-03-22 19:06:23 2013-03-22 19:06:23 CWoo (3771) CWoo (3771) 8 CWoo (3771) Example msc 94A60 msc 68Q45 msc 68Q05 msc 03D20