Computability and the language of arithmetic

1. Introduction

The Gödel incompleteness theorems are closly linked with computability theory. Not much computability theory is required to understand the connection, but this connection is best seen when one relates the idea of $Σ_{1}$ formulas to the idea of recursively enumerable sets (also sometimes called computably enumerable sets). This page reviews a small amount of computability theory and sets out the connection.

2. Recursively enumerable sets

Computability theory identifies an informal intuitive idea of what it means for a fuction or set to be computable with a precise machine model for computability, such as Turing machines or register machines. The fact that there are so many machine models known that capture the same notion of computable can be taken a evidence that the intuitive idea is indeed accurately captured by these models. Here I will take the idea of register machine, as it is a little more convenient for our purposes. The energetic reader will be able to verify that the register machine model does indeed correspond whith his/her favourite model, be it Turing machines, the lambda calculus, Kolmogorov machines, or whatever.

Definition.

A register machine has a finite number of registers $R_{0}, R_{1}, \dots$ each of which is capable of storing a natural number. It has a program which is a finite list of instructions labelled $I_{0}, I_{1}, \dots$ . Each instruction is of the type

$I_{k}$ : $R_{i} := R_{i} + 1$

$I_{k}$ : if $R_{i} > 0$ then $R_{i} := R_{i} - 1$ else goto $I_{j}$

In both cases, the next instruction to be execute is the next one on the list, $I_{k + 1}$ , unless the goto $I_{j}$ is performed. There is a last instruction, and if this last instruction is performed without any goto $I_{j}$ clause being executed then the machine instead of attempting to execute the next instruction (which doesn't exist) simply halts.

Definition.

A register machine computes a total function $f : ℕ \to ℕ$ if, for all $n \in ℕ$ , whenever it is started with $R_{0}$ containing $n$ and all other registers zero it eventually halts with $f (n)$ in $R_{0}$ . Similarly, it computes a partial function $f : ℕ \to ℕ$ (i.e. a function $f : A \to ℕ$ where $A \subseteq ℕ$ ) if, for all $n \in ℕ$ , whenever it is started with $R_{0}$ containing $n$ and all other registers zero, if $f (n)$ is defined (i.e. $n \in A$ ) then it eventually halts with $f (n)$ in $R_{0}$ and if $f (n)$ is not defined (i.e. $n \notin A$ ) then it goes on for ever.

We can modify the definition just given to computing (total or partial) functions $f : ℕ^{k} \to ℕ$ of several arguments by just requiring that $R_{0}, \dots, R_{k - 1}$ contain the arguments $n_{0}, \dots, n_{k - 1}$ of $f (n_{0}, \dots, n_{k - 1})$ .

Definition.

A (total or partial) function is computable or recursive if it can be computed by a register machine.

In the theory, total recursive functions and partial recursive functions behave quite differently and recursive function is reserved to mean total recursive function, the word partial if applicable being never omitted.

Definition.

If $A \subseteq ℕ$ its charactistic function $χ_{A} : ℕ \to \{0, 1\}$ is the total function with $f (n) = 1 \leftrightarrow n \in A \leftrightarrow f (n) \neq 0$ . A register machine computes the set $A$ if and only if it computes the characteristic function $χ_{A}$ . Similarly for $A \subseteq ℕ^{k}$ , $χ_{A} : ℕ^{k} \to \{0, 1\}$ is defined by $f (n_{0}, \dots, n_{k - 1}) = 1 \leftrightarrow (n_{0}, \dots, n_{k - 1}) \in A \leftrightarrow f (n_{0}, \dots, n_{k - 1}) \neq 0$ and $A$ is computed if and only if $χ_{A}$ is. A set that is computed by some register machine is called computable or recursive.

There is a weaker notion of computability that is also important.

Definition.

A set is recursively enumerable or r.e. if either it is empty or there is a (total) computable function $f : ℕ \to ℕ$ such that $A$ is the range of $f$ .

Exercise.

Show that that a set $A$ is r.e. if and only if there is a register machine which when started with $n$ in $R_{0}$ and all other registers zero then the machine halts if and only if $n \in A$ , and that this holds if and only if the partial function $f : A \to \{0\}$ is partial recursive.

Definition.

A set $A \subseteq ℕ$ is co-r.e. if its complement $ℕ - A$ is r.e.

Theorem.

A set $A$ is recursive if and only if it is both r.e. and co-r.e.

There is a convincing informal argument that says that this notion of computability really does capture the correct intuitive idea. This argument is due to Turing, for the idea of computability defined using Turing machines, but it can be adapted to register machines by simply showing how to simulate an arbitrary Turing machine by a register machine. The statement that this notion of computability is correct is known as Church's thesis or the Chruch-Turing thesis.

3. Arithmetic

The main theorem here says that a set is r.e. if and only if it is defined by a $Σ_{1}$ formula and is co-r.e. if and only if it is defined by a $Π_{1}$ formula. If we are to prove statements like this we must start by finding ways of expressing complicated predicates as $Δ_{0}$ formulas. This is how we start. The key result is due to Gödel and is often called the $β$ -function lemma. It expresses the well-known fact that there is an injection $ℕ^{< ω} \to ℕ$ from finite sequences of naturals to naturals, but the twist is that Gödel shows how to do this in such a way that the inverse map can be described by a $Δ_{0}$ formula.

We start first with something a little simpler.

Exercise.

Show that the function

⟨ u, v ⟩ = \frac{(u + v) (u + v + 1)}{2} + u

is a bijection $ℕ^{2} \to ℕ$ .

This function is (for obvious reasons) called the pairing function. Note that if $⟨ u, v ⟩ = x$ then $u, v < x + 1$ and the statement $⟨ u, v ⟩ = x$ is quantifier free, so is certainly $Δ_{0}$ .

Definition.

We write

z = rem (\frac{x}{y})

for $z < y \land \exists w < x + 1 (x = y w + z)$ . This formula is clearly $Δ_{0}$ and says that $z$ is the remainder on dividing $x$ by $y$ .

Exercise.

It is true (i.e. in $ℕ$ ) that $\forall x \forall y (y \neq 0 \to \exists z z = rem (\frac{x}{y}))$ . This statement is not however provable in $DOR$ .

Definition.

For $x, y \in ℕ$ , we let $β (x, y)$ be

rem (\frac{u}{v (y +1) + 1})

where $x = ⟨ u, v ⟩$ .

Lemma.

There is a $Δ_{0}$ formula defining $β (x, y) = z$ and for any $k \in ℕ$ and sequence $s = (s_{0}, \dots, s_{k - 1}) \in ℕ^{< ω}$ of length $k$ there is $x \in ℕ$ such that $\forall y < k s_{y} = β (x, y)$ .

There are a number of possible proofs of this. The original and perhaps the simplest uses the Chinese Remainder Theorem.

Theorem.

If $m_{0}, m_{1}, \dots, m_{k - 1}$ are positive integers and pairwise coprime and is $x_{i} \in ℕ$ for each $i$ then there is $x \in ℕ$ such that $x \equiv x_{i} mod m_{i}$ for each $i < k$ .

Proof.

Given $s \in ℕ^{< ω}$ , $s = (s_{0}, s_{1}, \dots s_{k - 1})$ , let $w = max (s_{0}, s_{1}, \dots s_{k - 1}, k)$ and $v = w!$ . So for $0 < i < j ⩽ k$ , if $p$ is prime and $p | (i v + 1)$ and $p | (j v + 1)$ then $i v + 1 = a p$ and $j v + 1 = b p$ for some $a, b \in ℕ$ with $b > a$ , so $(j - i) v = (b - a) p$ hence $p$ divides $(j - i) v$ . If $p$ divides $v$ then $p$ divides $i v$ and hence $p = 1$ since it also divides $i v + 1$ . So $p | j - i$ . In particular $p < k ⩽ w$ so $p$ divides $w! = v$ and once again this means $p$ equals $1$ . Thus there is no such prime $p$ and the moduli $i v + 1$ are coprime for $1 ⩽ i ⩽ k$ . Also $s_{i} ⩽ w < (i + 1) v + 1$ for all such $i$ , so by the Chinese Remainder Theorem there is $u$ with $s_{i} = rem (\frac{u}{(i + 1) v + 1})$ for all $0 ⩽ i < k$ .

Put $x = ⟨ u, v ⟩$ and we are finished, the $Δ_{0}$ formula $β (x, y) = z$ being

\exists u ⩽ x \exists v ⩽ x (2 u + (u + v) (U + v +1) = 2 x \land \exists t ⩽ u (u = t ((1 + y) v +1) + z) \land z < (1 + y) v + 1)

In particular for a sequence $s \in ℕ^{< ω}$ the map $s \mapsto ⟨ x, k ⟩$ defines an injection $ℕ^{< ω} \to ℕ$ , where $k$ is the length of $s$ and $x$ is the least natural number such that $\forall y < k s_{y} = β (x, y)$ .

The link with computability comes with the following consequence of Gödel's $β$ -function lemma.

Theorem.

Suppose $f : ℕ^{k} \to ℕ$ is a partial recursive function. Then there is a $Σ_{1}$ formula $θ (\overline{x}, y)$ such that for all $\overline{n}, m \in ℕ$ $ℕ ⊨ θ (\overline{n}, m)$ holds if and only if $f (\overline{n}) = m$ .

Proof.

The proof is by describing the action of a register machine using the $β$ function.

Given a register machine using registers $r_{0}, \dots, r_{n}$ we consider a formulas starting $\exists R_{0}, \dots, R_{n}, I, t \dots$ where $β (R_{i}, j)$ is the contents of $r_{i}$ at time $j$ , $β (I, j)$ is the index of the next instruction to be performed at time $j$ , and $t$ is the total time of the computation. Then the entire computation can be described in a $Δ_{0}$ way with formulas such as

$β (R_{i}, 0) = x_{i}$ , saying $r_{i}$ is initially $x_{i}$ ,
$β (R_{i}, t) = y$ , saying $r_{i}$ is at the end $y$ ,
$β (I_{i}, 0) = 0$ , saying the first instruction is performed first,
$β (I, i) = p \to β (R_{j}, i +1) = β (R_{j}, i) +1 \land β (I, i) = p +1$ , for the " $I_{p} : r_{j} := r_{j} + 1$ " instruction,
$β (I, i) = p \land β (R_{j}, i) > 0 \to β (R_{j}, i +1) +1 = β (R_{j}, i) \land β (I, i) = p +1$ , and $β (I, i) = p \land β (R_{j}, i) = 0 \to β (R_{j}, i +1) = β (R_{j}, i) \land β (I, i) = q$ , for the " $I_{p} : r_{j} := r_{j} - 1 else go to I_{q}$ " instruction,

and $β (R_{l}, i +1) = β (R_{l}, i)$ for all other $l$ , quantified over all $i < t$ .

Theorem.

A set $A \subseteq ℕ^{k}$ is r.e. if and only if it is defined by a $Σ_{1}$ formula. $A$ is co-r.e. if and only if it is defined by a $Π_{1}$ formula.

It follows that a set is recursive iff it is simultaneously defined by both a $Σ_{1}$ formula and a $Π_{1}$ formula.

Exercise.

Find a recursive set that is not definable by a $Δ_{0}$ formula. Hint: show that the set of $(n, m)$ , such that $n$ is the Gödel-number of a $Δ_{0}$ sentence $θ_{n} (x)$ and $θ_{n} (m)$ is true, is recursive.