# primitive recursive encoding

Recall that an encoding of a set $L$ of words over some alphabet $\Sigma$ is defined as an injective function $E:L\to\mathbb{N}$, the set of natural numbers (including $0$ here).

Finite sequences over $\mathbb{N}$ can be thought of as words over the “infinite” alphabet $\mathbb{N}$. So the notion of word encoding directly carries over to encoding of finite sequences of natural numbers. Let $\mathbb{N}^{*}$ be the set of all finite sequences over $\mathbb{N}$.

Definition. Let $E$ be an encoding for $\mathbb{N}^{*}$. A number is called a sequence number if it is in the range of $E$. Since $E$ is injective, we say that $E(a)$ is the sequence number of the sequence $a$.

Once $E$ is fixed, we also use the notation $\langle a_{1},\ldots,a_{k}\rangle$ to mean the sequence number of the sequence $a_{1},\ldots,a_{k}$.

Define the following operations on $\mathbb{N}$ associated with a given $E$:

1. 1.

$E_{n}:=E|\mathbb{N}^{*}_{n}$, the restriction of $E$ to the set $\mathbb{N}^{*}_{n}$ of all sequences of length $n$, and $E_{0}$ is defined as the number $\langle\rangle$.

2. 2.

the length function: $\operatorname{lh}:\mathbb{N}\to\mathbb{N}$:

 $\operatorname{lh}(x):=\left\{\begin{array}[]{ll}z,&\textrm{if }E^{-1}(x)% \textrm{ exists, and has length }z,\\ 0,&\textrm{otherwise}.\end{array}\right.$
3. 3.

$(\cdot)_{\cdot}:\mathbb{N}^{2}\to\mathbb{N}$, such that

 $(x)_{y}:=\left\{\begin{array}[]{ll}z,&\textrm{if }E^{-1}(x)\textrm{ exists, % has length }\geq y\textrm{, with }z\textrm{ its }y\textrm{-th number},\\ 0,&\textrm{otherwise}.\end{array}\right.$
4. 4.

$*:\mathbb{N}^{2}\to\mathbb{N}$, such that

 $x*y:=\left\{\begin{array}[]{ll}E(ab),&\textrm{where }E(a)=x\textrm{ and }E(b)=% y,\\ 0,&\textrm{otherwise}.\end{array}\right.$

The notation $ab$ stands for the concatenation of the sequences $a$ and $b$.

5. 5.

$\operatorname{ext}:\mathbb{N}^{2}\to\mathbb{N}$, such that

 $\operatorname{ext}(x,y):=\left\{\begin{array}[]{ll}E(ay),&\textrm{where }E(a)=% x,\\ 0,&\textrm{otherwise}.\end{array}\right.$

The notation $ay$ stands for the sequence $a$, extended by appending $y$ to the right of $a$.

6. 6.

$\operatorname{red}:\mathbb{N}\to\mathbb{N}$, such that

 $\operatorname{red}(x):=\left\{\begin{array}[]{ll}z,&\textrm{where }E(a)=x% \textrm{ and }E(b)=z\textrm{ such that }a=bc\textrm{ and }c\in\mathbb{N},\\ 0,&\textrm{otherwise}.\end{array}\right.$

In other words, $z$ is the sequence number of the sequence obtained by removing the last (rightmost) number (if any) in the sequence whose sequence number is $x$, provided that $x$ is a sequence number.

Definition. An encoding $E$ for $\mathbb{N}^{*}$ is said to be primitive recursive if

• $E(\mathbb{N}^{*})$ is a primitive recursive set, and

• the first three types of functions defined above are primitive recursive.

###### Proposition 1.

If $E$ is primitive recursive, so are the functions $*,\operatorname{ext}$, and $\operatorname{red}$.

###### Proof.

Let $\chi(x)$ be the characteristic function of the predicate$x$ is a sequence number” (via $E$). It is primitive recursive by assumption.

1. 1.

Let $n=\operatorname{lh}(x)+\operatorname{lh}(y)$. Then $x*y=E_{n}((x)_{1},\ldots,(x)_{\operatorname{lh}(x)},(y)_{1},\ldots,(y)_{% \operatorname{lh}(y)})\cdot\chi(x)\chi(y)$, which is primitive recursive.

2. 2.

Let $n=\operatorname{lh}(x)+1$. Then $\operatorname{ext}(x,y)=E_{n}((x)_{1},\ldots,(x)_{\operatorname{lh}(x)},y)\chi% (x)$, which is primitive recursive.

3. 3.

Let $n=\operatorname{lh}(x)\dot{-}1$. Then

 $\operatorname{red}(x)=\left\{\begin{array}[]{ll}E_{n}((x)_{1},\ldots,(x)_{% \operatorname{lh}(x)\dot{-}1}),&\textrm{if }\operatorname{lh}(x)>1\textrm{, % and }\chi(x)=1\\ \langle\rangle,&\textrm{if }\operatorname{lh}(x)=1\textrm{, and }\chi(x)=1\\ 0,&\textrm{otherwise},\end{array}\right.$

which is primitive recursive.

Examples of primitive recursive encoding can be found in the parent entry (methods 2, 3, and 7).

Title primitive recursive encoding PrimitiveRecursiveEncoding 2013-03-22 19:06:20 2013-03-22 19:06:20 CWoo (3771) CWoo (3771) 7 CWoo (3771) Definition msc 68Q05 msc 68Q45 msc 03D20 msc 94A60 sequence number