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.

$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.

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.

$(\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.

$*:\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 $a b$ stands for the concatenation of the sequences $a$ and $b$ .
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 $a y$ stands for the sequence $a$ , extended by appending $y$ to the right of $a$ .
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.

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.

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.

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
Canonical name	PrimitiveRecursiveEncoding
Date of creation	2013-03-22 19:06:20
Last modified on	2013-03-22 19:06:20
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	7
Author	CWoo (3771)
Entry type	Definition
Classification	msc 68Q05
Classification	msc 68Q45
Classification	msc 03D20
Classification	msc 94A60
Defines	sequence number