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,\mathrm{\dots },a_k$, its image under $E$ is denoted by $⟨a_1,\mathrm{\dots },a_k⟩$, and is called the sequence number corresponding to $a_1,\mathrm{\dots },a_k$. Furthermore, $()$ denotes the empty sequence, and its sequence number is denoted by $⟨⟩$. 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:

$⟨⟩$ $:=$ $1,$

$⟨a_1,\mathrm{\dots },a_k⟩$ $:=$ $p_1^{s(a_1)}\mathrm{\cdots }{p}_k^{s(a_k)},$

where $s$ is the successor function, and $p_1,\mathrm{\dots },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\le p$. The predicates

  $${\mathrm{\Phi }}_1:=\mathrm{`}\mathrm{`}p|x\text{ for some prime }p\text{”}\equiv \mathrm{`}\mathrm{`}\exists p\le x(P(p)\wedge (p|x))\text{”},$$

  $${\mathrm{\Phi }}_2:=\mathrm{`}\mathrm{`}p\text{ is prime and }q|x\text{ for all primes }q\le p\text{”}\equiv \mathrm{`}\mathrm{`}\forall q\le p(P(p)\wedge P(q)\wedge (q|x))\text{”}$$

  where $P(r):=$ “$r$ is prime”, are primitive recursive by bounded quantification. Thus “$x$ is a sequence number” iff “$x=1$ or ${\mathrm{\Phi }}_1\to {\mathrm{\Phi }}_2$” iff “$(x=1)\vee (\mathrm{\neg }{\mathrm{\Phi }}_1\vee {\mathrm{\Phi }}_2)$”, is primitive recursive as a result.

• $E_k(a_1,\mathrm{\dots },a_k):=p_1^{s(a_1)}\mathrm{\cdots }{p}_k^{s(a_k)}$ is clearly primitive recursive.

• $\mathrm{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\ge 2$, define

$J_2(x_1,x_2)$ $:=$ $J(x_1,x_2)$

$J_{n+1}(x_1,\mathrm{\dots },x_n,x_{n+1})$ $:=$ $J(x_1,J_n(x_2,\mathrm{\dots },x_{n+1})).$

Then define $E$ by

$⟨⟩$ $:=$ $0,$

$⟨a_1,\mathrm{\dots },a_k⟩$ $:=$ $J(k,J_k(a_1,\mathrm{\dots },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,\mathrm{\dots },a_k):=J(k,J_k(a_1,\mathrm{\dots },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 $\mathrm{lh}(x)=L(x)$ in particular is primitive recursive.

• If $J_k(a_1,\mathrm{\dots },a_k)=b$, then $a_1=L(b),a_2=LRL(b),\mathrm{\dots },a_{k-1}={(LR)}^{k-2}L(b)$, and $a_k=R{(LR)}^{k-2}L(b)$. Thus,

  is primitive recursive, since each case is primitive recursive.

Example 3. (Digital Representation) Pick a positive integers $p>1$. Define $E$ by

$⟨⟩$ $:=$ $1$

$⟨a⟩$ $:=$ $p^{s(a)}$

$⟨a_1,\mathrm{\dots },a_k,a_{k+1}⟩$ $:=$ $⟨a_1⟩(⟨a_2,\mathrm{\dots },a_{k+1}⟩+1).$

In other words,

$$⟨a_1,\mathrm{\dots },a_k⟩=p^{s(a_1)}+p^{s(a_1)+s(a_2)}+\mathrm{\cdots }{p}^{s(a_1)+\mathrm{\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):=\mathrm{lo}(p,x)$, the exponent of $p$ in $x$, $g:\mathbb{N}\to \mathbb{N}$ given by $g(x):=\mathrm{quo}(x,p^{f(x)})\dot{-}1$, and $h:{\mathbb{N}}^2\to \mathbb{N}$ given by

$h(x,0)$ $:=$ $x$

$h(x,n+1)$ $:=$ $g(h(x,n)).$

Clearly, $f,g,h$ are all primitive recursive. Furthermore, $h$ has the property that if $h(x,n)>0$, then , 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 np|h(x,n)))$”

  which is equivalent to the predicate

  “$(x=1)\vee ((x>0)\wedge (\forall n\le xp|h(x,n)))$”

  since $p>1$. As the quantification is bounded, the predicate is primitive recursive.

• $E_k(a_1,\mathrm{\dots },a_k)=⟨a_1,\mathrm{\dots },a_k⟩$ is primitive recursive by equation (1) above.

• $\mathrm{lh}(x)$ can be defined as the number of $n$ such that $h(x,n)\ne 0$, or

  $$\sum _{i=0}^x\mathrm{sgn}(h(x,i)),$$

  which is primitive recursive, because it is a bounded sum.

• If $⟨a_1,\mathrm{\dots },a_k⟩=x$, then $f(h(x,0))=s(a_1),\mathrm{\dots },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

$$⟨a_1,\mathrm{\dots },a_k,a_{k+1}⟩:=⟨a_1⟩(r⟨a_2,\mathrm{\dots },a_{k+1}⟩+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
Canonical name	ExamplesOfPrimitiveRecursiveEncoding
Date of creation	2013-03-22 19:06:23
Last modified on	2013-03-22 19:06:23
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	8
Author	CWoo (3771)
Entry type	Example
Classification	msc 94A60
Classification	msc 68Q45
Classification	msc 68Q05
Classification	msc 03D20