Coding finite sequences · Computability Theory

Programs manipulate lists, stacks and arrays of unbounded size, while the functions we study take a fixed number of integer arguments. We now show that finite sequences of integers can be coded by single integers, in such a way that all the usual operations on sequences become primitive recursive. This coding is used constantly: to describe configurations of machines, to code programs and formulas, and to define functions by recursion on all previous values.

Cantor’s pairing function already codes pairs, and by iteration tuples of a fixed length. Here the length is part of the data.

6.1 Prime power coding

We write $p_0 = 2, p_1 = 3, p_2 = 5, \dots$ for the primes and $(x)_i$ for the exponent of $p_i$ in $x \geq 1$ ; both are primitive recursive by the previous lesson.

Definition 6.1.#

The code of the finite sequence $(a_0, \dots, a_{n-1})$ of integers is

[a_0, \dots, a_{n-1}] = \prod_{i < n} p_i^{\,a_i + 1} = 2^{a_0 + 1} \cdot 3^{a_1 + 1} \cdots p_{n-1}^{\,a_{n-1} + 1}.

The empty sequence has code $[\,] = 1$ .

By the uniqueness of prime factorizations, the coding is injective. The exponents are shifted by one so that a sequence ending with zeros, such as $(5, 0)$ , has a different code from $(5)$ : indeed $[5] = 2^6$ while $[5, 0] = 2^6 \cdot 3$ . The coding is not surjective — $0$ , $3$ or $10$ are not codes — but the set of codes is primitive recursive.

Proposition 6.2.#

The following functions and predicates are primitive recursive:

the length $\mathrm{lh}(s)$ , equal to $n$ if $s = [a_0, \dots, a_{n-1}]$ ;
the projection $(s)'_i$ , equal to $a_i$ if $s = [a_0, \dots, a_{n-1}]$ and $i < n$ ;
the predicate $\mathrm{Seq}(s)$ : ” $s$ is the code of a sequence”;
the concatenation $s * t$ , with $[a_0, \dots, a_{n-1}] * [b_0, \dots, b_{m-1}] = [a_0, \dots, a_{n-1}, b_0, \dots, b_{m-1}]$ ;
the restriction $s \upharpoonright m$ , equal to $[a_0, \dots, a_{m-1}]$ for $m \leq n$ ;
the update $\mathrm{set}(s, i, v)$ , equal to the code of the sequence obtained by replacing $a_i$ with $v$ , for $i < n$ .

(The values on arguments that are not codes, or out of range, are irrelevant; the definitions below give some primitive recursive value.)

Proof of Proposition 6.2.

The exponents of a code are non-zero exactly on an initial segment of the primes, so $\mathrm{lh}(s) = \mu i < s\ ((s)_i = 0)$ . The bound is correct since $s \geq 2^{\mathrm{lh}(s)} > \mathrm{lh}(s)$ for a code $s$ .
$(s)'_i = (s)_i \dotminus 1$ .
$\mathrm{Seq}(s) \iff s \geq 1 \wedge \forall i < s\ \big( (s)_i \neq 0 \leftrightarrow i < \mathrm{lh}(s) \big)$ . The quantifier can be bounded by $s$ since $(s)_i = 0$ for $p_i > s$ , and $p_i > i$ .
$s * t = s \cdot \prod_{j < \mathrm{lh}(t)} p_{\mathrm{lh}(s) + j}^{\,(t)_j}$ .
$s \upharpoonright m = \prod_{i < m} p_i^{\,(s)_i}$ .
$\mathrm{set}(s, i, v) = \lfloor s / p_i^{(s)_i} \rfloor \cdot p_i^{\,v + 1}$ .

Each expression is built from primitive recursive functions using bounded sums, products and minimization.

6.2 Course-of-values recursion

Primitive recursion defines $f(\vec x, y + 1)$ from the single previous value $f(\vec x, y)$ . Many natural definitions use all previous values — the Fibonacci sequence uses two of them, and the definition of the code of a formula uses the codes of all its subformulas. Sequence coding reduces such definitions to primitive recursion.

Definition 6.3.#

For $f : \nat^{k+1} \to \nat$ , its course-of-values function is

\bar f(\vec x, y) = [f(\vec x, 0), f(\vec x, 1), \dots, f(\vec x, y - 1)].

Theorem 6.4 (Course-of-values recursion).#

Let $h : \nat^{k+2} \to \nat$ be primitive recursive. Then the function $f$ defined by

f(\vec x, y) = h(\vec x, y, \bar f(\vec x, y))

is primitive recursive.

Proof of Theorem 6.4.

The equation determines $f(\vec x, y)$ by induction on $y$ , since $\bar f(\vec x, y)$ only involves values at arguments smaller than $y$ . The function $\bar f$ satisfies the primitive recursion

\begin{gathered} \bar f(\vec x, 0) = 1, \\ \bar f(\vec x, y + 1) = \bar f(\vec x, y) \cdot p_y^{\,h(\vec x, y, \bar f(\vec x, y)) + 1}, \end{gathered}

so $\bar f$ is primitive recursive. Finally $f(\vec x, y) = (\bar f(\vec x, y + 1))'_y$ .

As an example, the Fibonacci sequence satisfies $\mathrm{fib}(y) = h(y, \overline{\mathrm{fib}}(y))$ where $h(y, s) = y$ if $y \leq 1$ and $h(y, s) = (s)'_{y-1} + (s)'_{y-2}$ otherwise.

6.3 Gödel’s β-function

The prime power coding uses exponentiation. In the proof of the incompleteness theorems, Gödel needed to code sequences using only addition and multiplication, because these are the only operations of the language of arithmetic. His solution relies on the Chinese remainder theorem.

Definition 6.5.#

Gödel’s β-function is $\beta(c, d, i) = c \bmod \big(1 + (i + 1) d\big)$ .

Lemma 6.6 (Gödel).#

For every finite sequence $a_0, \dots, a_{n-1}$ of integers there exist $c, d$ such that $\beta(c, d, i) = a_i$ for all $i < n$ .

Proof of Lemma 6.6.

Let $m = \max(n, a_0, \dots, a_{n-1})$ and $d = m!$ . We claim that the moduli $u_i = 1 + (i+1)d$ , for $i < n$ , are pairwise coprime. Suppose that a prime $q$ divides $u_i$ and $u_j$ with $i < j < n$ . Then $q$ divides $u_j - u_i = (j - i) d$ , so $q$ divides $j - i$ or $d$ . Since $1 \leq j - i \leq n \leq m$ , the integer $j - i$ divides $m! = d$ ; in both cases $q$ divides $d$ . But then $q$ divides $u_i - (i+1)d = 1$ , which is absurd.

By the Chinese remainder theorem there is $c$ such that $c \equiv a_i \pmod{u_i}$ for all $i < n$ . Since $a_i \leq m \leq d < u_i$ , the remainder of $c$ modulo $u_i$ is exactly $a_i$ , that is $\beta(c, d, i) = a_i$ .

The function $\beta$ is defined from $+$ , $\cdot$ and the remainder, and the relation $\beta(c, d, i) = a$ is expressible by the arithmetic formula $\exists q \leq c\ \big(c = q \cdot (1 + (i+1) d) + a \wedge a < 1 + (i+1) d\big)$ . This is how sequences, and hence computations, are represented in first-order arithmetic.

6.4 Exercises

Exercise 6.7 ★.

Show that the following predicates are primitive recursive: ” $s$ codes a strictly increasing sequence”; ” $s$ codes a prefix of the sequence coded by $t$ ”.

Solution

$\mathrm{Seq}(s) \wedge \forall i < \mathrm{lh}(s)\ \forall j < \mathrm{lh}(s)\ (i < j \rightarrow (s)'_i < (s)'_j)$ . For prefixes: $\mathrm{Seq}(s) \wedge \mathrm{Seq}(t) \wedge \mathrm{lh}(s) \leq \mathrm{lh}(t) \wedge \forall i < \mathrm{lh}(s)\ (s)'_i = (t)'_i$ .

Exercise 6.8 ★★.

Show that the function which maps the code of a sequence to the code of the same sequence sorted in non-decreasing order is primitive recursive.

Hint

Bound the code of the sorted sequence in terms of $s$ , and search for it.

Solution

The sorted sequence has the same length $n$ and the same entries, so its code is at most $\prod_{i < n} p_i^{M + 1}$ where $M = \max_i (s)'_i$ , a primitive recursive function $b(s)$ of $s$ . The sorted code is $\mu t < b(s) + 1\ \big(\mathrm{Seq}(t) \wedge \mathrm{lh}(t) = \mathrm{lh}(s) \wedge t \text{ is non-decreasing} \wedge \forall v \leq M\ \#_v(t) = \#_v(s)\big)$ , where $\#_v(s) = \sum_{i < \mathrm{lh}(s)} \chi_=((s)'_i, v)$ counts the occurrences of $v$ . All of this is primitive recursive.

Exercise 6.9 ★★.

Define a bijective coding of finite sequences: show that the function $\langle\!\langle \cdot \rangle\!\rangle$ given by $\langle\!\langle \, \rangle\!\rangle = 0$ and $\langle\!\langle a_0, \dots, a_{n} \rangle\!\rangle = 1 + \langle a_0, \langle\!\langle a_1, \dots, a_n \rangle\!\rangle \rangle$ is a bijection between finite sequences and $\nat$ , and that its length and projection functions are primitive recursive.

Solution

By induction on $z$ : $z = 0$ codes only the empty sequence, and $z \geq 1$ codes exactly the sequences with first element $\pi_0(z - 1)$ followed by a sequence coded by $\pi_1(z - 1)$ , which is smaller than $z$ since $\langle x, y \rangle \geq y$ ; by the induction hypothesis there is exactly one such sequence, which gives existence and uniqueness. The length satisfies $\mathrm{lh}(0) = 0$ and $\mathrm{lh}(z) = 1 + \mathrm{lh}(\pi_1(z - 1))$ for $z \geq 1$ , a course-of-values recursion since $\pi_1(z - 1) < z$ ; by Theorem 6.4, $\mathrm{lh}$ is primitive recursive. For the projections, the parameter changes along the recursion, so it is simpler to iterate the tail: let $\mathrm{tl}(z, 0) = z$ and $\mathrm{tl}(z, i + 1) = \pi_1(\mathrm{tl}(z, i) \dotminus 1)$ , a primitive recursion on $i$ . If $z$ codes $(a_0, \dots, a_n)$ and $i \leq n$ , then $\mathrm{tl}(z, i)$ codes $(a_i, \dots, a_n)$ , so $a_i = \pi_0(\mathrm{tl}(z, i) \dotminus 1)$ .

6.5 Notes and references

The β-function lemma appears in Gödel’s incompleteness paper of 1931, where it is used to express definitions by recursion in the language of arithmetic. Coding finite sequences by prime powers is also due to Gödel. Course-of-values recursion is treated in detail in Péter’s monograph.

K. Gödel, Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I, Monatshefte für Mathematik und Physik 38 (1931), 173–198.
S. C. Kleene, Introduction to Metamathematics, North-Holland, 1952.