Programs as numbers · Computability Theory

The course on models of computation ends with an enumeration of all partial computable functions: machines are coded by integers, and the function computed by the machine of code $e$ is obtained from $e$ by a single unbounded search (Kleene's normal form). The whole of computability theory is built on this enumeration. This lesson fixes it once and for all, together with its approximation by stages, and sets up the notions of computable set and computable relation. From now on, algorithms are described in words or pseudo-code, following the practice explained in The Church–Turing thesis.

1.1 The enumeration

Recall that $T_k(e, \vec x, s)$ is the primitive recursive predicate ” $s$ codes the complete computation of the machine of code $e$ on input $\vec x = (x_1, \dots, x_k)$ ”, that for given $e$ and $\vec x$ at most one $s$ satisfies it, and that $U(s)$ is the primitive recursive function reading the output on the last configuration of the computation coded by $s$ . Integers that do not code a machine are treated as coding a fixed machine that never halts, so that every integer is the code of a machine.

Notation 1.1.#

For $e \in \nat$ and $k \geq 1$ , $\Phi^{(k)}_e$ is the $k$ -ary partial function

\Phi^{(k)}_e(\vec x) \simeq U\big(\mu s\ T_k(e, \vec x, s)\big),

computed by the machine of code $e$ . The integer $e$ is an index of $\Phi^{(k)}_e$ . The superscript is omitted when the number of arguments is clear, and $\Phi_e$ stands for $\Phi^{(1)}_e$ . For an input $\vec x$ :

$\Phi_e(\vec x)\converge$ means that the computation halts in a standard configuration, so that $\Phi_e(\vec x)$ is defined; $\Phi_e(\vec x)\diverge$ means that it is undefined;
$\Phi_e(\vec x)\converge = y$ means that it is defined, with value $y$ .

By Universal function, the sequence $\Phi_0, \Phi_1, \Phi_2, \dots$ contains every unary partial computable function, and the map $(e, \vec x) \mapsto \Phi_e(\vec x)$ is itself partial computable. These two facts — every partial computable function has an index, and the enumeration is computable — are the only properties of the enumeration used in most of the theory. The next lesson adds a third one, the SMN theorem.

Notation 1.2.#

As in the course on models of computation (Notation 1.2 of “Algorithms and partial functions”), $\alpha \simeq \beta$ between two expressions denoting possibly undefined values means: either both are defined and equal, or both are undefined. For partial functions, $f = g$ means $f(\vec x) \simeq g(\vec x)$ for every $\vec x$ : the two functions have the same domain and agree on it.

The domain of a partial function $f$ is $\mathrm{dom}(f) = \{ \vec x : f(\vec x)\converge \}$ , and its graph is $\{ (\vec x, y) : f(\vec x)\converge = y \}$ . A partial function is total if its domain is the set of all inputs.

1.2 Approximation by stages

The computation of $\Phi_e(x)$ can be followed for a while. The following definition makes this precise, with conventions that make the approximations finite objects.

Definition 1.3.#

For $e, x, s \in \nat$ , let

\Phi_e(x)[s] \simeq \begin{cases} U(t) & \text{if } e, x < s \text{ and } T_1(e, x, t) \text{ for some } t < s,\\ \text{undefined} & \text{otherwise.}\end{cases}

We say that $\Phi_e(x)$ converges at stage $s$ when $\Phi_e(x)[s]\converge$ . The same notation is used for several arguments, with $T_k$ in place of $T_1$ .

Since a computation of $t$ steps has a code larger than $t$ , convergence at stage $s$ implies that the computation halts in fewer than $s$ steps. The precise relation between stages and steps is irrelevant: what matters is the following.

Proposition 1.4.#

The relation $\Phi_e(x)[s]\converge = y$ , of the variables $e, x, s, y$ , is primitive recursive. In particular, given $e$ , $x$ and $s$ , one can decide whether $\Phi_e(x)[s]\converge$ , and compute its value if so.
If $\Phi_e(x)[s]\converge = y$ and $s' \geq s$ , then $\Phi_e(x)[s']\converge = y$ .
$\Phi_e(x)\converge = y$ if and only if $\Phi_e(x)[s]\converge = y$ for some $s$ .

Proof of Proposition 1.4.

$\Phi_e(x)[s]\converge = y$ holds if and only if $e < s \wedge x < s \wedge \exists t < s\, \big(T_1(e, x, t) \wedge U(t) = y\big)$ . This is obtained from primitive recursive predicates by Boolean operations and a bounded quantifier, hence it is primitive recursive (Corollary 5.10 of “Primitive recursive functions”). The value, when defined, is $U(\mu t < s\ T_1(e, x, t))$ , a bounded minimization.
The witness $t < s$ is also smaller than $s'$ , and the conditions $e, x < s$ are preserved.
If $\Phi_e(x)\converge = y$ , let $t$ be the code of the computation; then $T_1(e, x, t)$ and $U(t) = y$ , so $\Phi_e(x)[s]\converge = y$ for $s = \max(e, x, t) + 1$ . Conversely, if $\Phi_e(x)[s]\converge = y$ with witness $t$ , then $t$ is the unique $t$ with $T_1(e, x, t)$ , so $\mu u\, T_1(e, x, u) = t$ and $\Phi_e(x) = U(t) = y$ .

The contrast between items 1 and 3 is the central phenomenon of the theory. Convergence at a given stage is decidable; convergence is the existence of a stage, a question with an unbounded quantifier, and it is not decidable, as the lesson on the halting problem shows. Divergence is never confirmed at a finite stage: $\Phi_e(x)\diverge$ means $\Phi_e(x)[s]\diverge$ for every $s$ .

1.3 Computable sets and relations

Definition 1.5.#

A relation $R \subseteq \nat^k$ is computable (or decidable) if its characteristic function, equal to $1$ on $R$ and $0$ outside, is computable: there is an $e$ such that $\Phi^{(k)}_e$ is total and $\Phi^{(k)}_e(\vec x) = 1$ if $\vec x \in R$ , $\Phi^{(k)}_e(\vec x) = 0$ otherwise. For $k = 1$ one speaks of computable sets.

Computable sets were called recursive in older texts, after the partial recursive functions, and the expressions recursion theory and recursive set are still used. We freely identify a relation $R \subseteq \nat^k$ with the set $\{ \langle x_1, \dots, x_k \rangle : \vec x \in R \}$ , obtained through the pairing function; one is computable if and only if the other is.

Proposition 1.6.#

The computable relations are closed under complement, finite union and finite intersection, and under substitution of total computable functions: if $R \subseteq \nat^m$ is computable and $g_1, \dots, g_m : \nat^k \to \nat$ are total computable, then $\{ \vec x : (g_1(\vec x), \dots, g_m(\vec x)) \in R \}$ is computable.
They are closed under bounded quantification: if $R \subseteq \nat^{k+1}$ is computable, so are $\{ (\vec x, y) : \exists z < y\ R(\vec x, z) \}$ and $\{ (\vec x, y) : \forall z < y\ R(\vec x, z) \}$ .
Definition by cases: if $R_1, \dots, R_n$ are computable relations partitioning $\nat^k$ and $g_1, \dots, g_n$ are partial computable, then $f(\vec x) \simeq g_i(\vec x)$ for $\vec x \in R_i$ defines a partial computable function.
Unbounded search: if $R \subseteq \nat^{k+1}$ is computable, then $f(\vec x) \simeq \mu y\, R(\vec x, y)$ is partial computable, and total if for every $\vec x$ there is some $y$ with $R(\vec x, y)$ .

Proof of Proposition 1.6.

By Equivalence of the models, the computable partial functions are the partial recursive functions, which contain the primitive recursive functions and are closed under composition, primitive recursion and minimization. Let $\chi_R$ denote the characteristic function of $R$ .

$\chi_{\nat^k \setminus R} = 1 \dotminus \chi_R$ , $\chi_{R \cap S} = \chi_R \cdot \chi_S$ , and unions are complements of intersections of complements. Substitution is composition: the characteristic function of the new relation is $\chi_R(g_1(\vec x), \dots, g_m(\vec x))$ , which is total.
The function $(\vec x, y) \mapsto \sum_{z < y} \chi_R(\vec x, z)$ is defined by primitive recursion from $\chi_R$ , hence computable, and $\exists z < y\ R(\vec x, z)$ holds exactly when it is non-zero. The bounded universal quantifier is the complement of a bounded existential quantifier applied to the complement.
On input $\vec x$ , compute $\chi_{R_1}(\vec x), \dots, \chi_{R_n}(\vec x)$ , which are all defined, find the unique $i$ with $\vec x \in R_i$ , and compute $g_i(\vec x)$ . Only the branch that applies is evaluated, so the result is undefined exactly when $g_i(\vec x)$ is.
$f(\vec x) \simeq \mu y\, [1 \dotminus \chi_R(\vec x, y) = 0]$ is a minimization of a total computable function. It is defined exactly when some $y$ satisfies $R(\vec x, y)$ .

In item 3, the evaluation of only one branch matters: in the primitive recursive definition by cases of the course on models of computation, all branches are computed, which is harmless for total functions but not for partial ones.

1.4 Uniformity

A typical statement of computability theory asserts that some object is obtained uniformly from others: for instance, “the set $A_x$ is computable, uniformly in $x$ ” means that the relation $\{ (x, y) : y \in A_x \}$ is computable, and not only that each $A_x$ is computable. The difference is essential. Let $\emptyset' = \{ e : \Phi_e(e)\converge \}$ be the halting set, which is not computable (Theorem 3.2, in the lesson on the halting problem). Each set $A_x = \{ 0 \}$ if $x \in \emptyset'$ and $A_x = \emptyset$ otherwise is finite, hence computable; but the relation $y \in A_x$ is not, since $x \in \emptyset'$ if and only if $0 \in A_x$ . Similarly, an index $e$ “obtained uniformly in $x$ ” is the value of a total computable function of $x$ .

1.5 Exercises

Exercise 1.7 ★.

Let $f : \nat \to \nat$ be total. Show that $f$ is computable if and only if its graph is computable.

Solution

If $f$ is computable, $f(x) = y$ is decided by computing $f(x)$ and comparing with $y$ . Conversely, if the graph $G$ is computable, then $f(x) = \mu y\ G(x, y)$ , a search that terminates since $f$ is total; it is computable by Proposition 1.6.

Exercise 1.8 ★.

Show that the set $\{ e : \Phi_e(0)[e]\converge \}$ is computable, and that the function $s \mapsto |\{ e < s : \Phi_e(e)[s]\converge \}|$ is total computable.

Solution

Both follow from item 1 of Proposition 1.4. The first set is defined by substituting $(e, 0, e)$ in a primitive recursive relation. The function is $\sum_{e < s} \chi(e, s)$ , where $\chi(e, s)$ is the characteristic function of the primitive recursive relation $\Phi_e(e)[s]\converge$ ; it is primitive recursive.

Exercise 1.9 ★★.

Show that a partial computable function with a computable domain has a total computable extension. Show by an example that a partial computable function may have a total computable extension and a non-computable domain.

Solution

If $D = \mathrm{dom}(f)$ is computable, let $g(x) \simeq f(x)$ for $x \in D$ and $g(x) = 0$ for $x \notin D$ , a definition by cases (Proposition 1.6); $g$ is total since $f(x)\converge$ for $x \in D$ . For the converse, consider the partial function defined by $f(e) \simeq 0$ if $\Phi_e(e)\converge$ , undefined otherwise. It is partial computable, its domain $\emptyset'$ is not computable (Theorem 3.2), and the constant function $0$ is a total computable extension.

1.6 Notes and references

The enumeration of the partial recursive functions by indices, and the normal form theorem on which it rests, are due to Kleene (1936, 1938). The notation $\Phi_e$ follows Soare’s textbook; Rogers writes $\varphi_e$ . The approximation by stages and its conventions are standard in modern texts, where they are the basis of all constructions by stages.

S. C. Kleene, General recursive functions of natural numbers, Mathematische Annalen 112 (1936), 727–742.
S. C. Kleene, On notation for ordinal numbers, Journal of Symbolic Logic 3 (1938), 150–155.
H. Rogers, Theory of Recursive Functions and Effective Computability, McGraw-Hill, 1967.
R. I. Soare, Turing Computability: Theory and Applications, Springer, 2016.