primitive recursive encoding

Recall that an encoding of a set $L$ of words over some alphabet $\mathrm{\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 $⟨a_1,\mathrm{\dots },a_k⟩$ to mean the sequence number of the sequence $a_1,\mathrm{\dots },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 $⟨⟩$.

2. the length function: $\mathrm{lh}:\mathbb{N}\to \mathbb{N}$:

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

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

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

5. $\mathrm{ext}:{\mathbb{N}}^2\to \mathbb{N}$, such that

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

6. $\mathrm{red}:\mathbb{N}\to \mathbb{N}$, such that

   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 $\mathrm{*}\mathrm{,}\mathrm{ext}$, and $\mathrm{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=\mathrm{lh}(x)+\mathrm{lh}(y)$. Then $x*y=E_n({(x)}_1,\mathrm{\dots },{(x)}_{\mathrm{lh}(x)},{(y)}_1,\mathrm{\dots },{(y)}_{\mathrm{lh}(y)})\cdot \chi (x)\chi (y)$, which is primitive recursive.

2. Let $n=\mathrm{lh}(x)+1$. Then $\mathrm{ext}(x,y)=E_n({(x)}_1,\mathrm{\dots },{(x)}_{\mathrm{lh}(x)},y)\chi (x)$, which is primitive recursive.

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

   which is primitive recursive.

∎

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