You are here
Homeprimitive recursive encoding
Primary tabs
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 $ab$ 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 $ay$ 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
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).
Mathematics Subject Classification
68Q05 no label found68Q45 no label found03D20 no label found94A60 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