Diagonalization and computation · Computability Theory

This lesson connects the previous ones with computation. Counting shows that almost all functions are not computable, but it exhibits none. Diagonalization does better: applied to an enumeration that is itself computable, it produces a function that is computable, and escapes the enumeration. Applied to the enumeration $\Phi_0, \Phi_1, \Phi_2, \dots$ of all partial computable functions, it does not produce a contradiction, but a point of divergence, and from there the undecidability of the halting problem. The last section presents diagonalization as the satisfaction of a list of requirements, the form in which it is used in the rest of computability theory.

We use the notation of the course on models of computation: $\Phi_e$ is the partial function computed by the program of code $e$ , and $\Phi(e, x) \simeq \Phi_e(x)$ is partial computable (Universal function). We write $\Phi_e(x)\converge$ when the computation halts and $\Phi_e(x)\diverge$ otherwise.

6.1 Counting

Proposition 6.1.#

The set of partial computable functions $\nat \rightharpoonup \nat$ , the set of total computable functions $\nat \to \nat$ and the set of computable subsets of $\nat$ are countably infinite.

Proof of Proposition 6.1.

By Universal function, every partial computable function is $\Phi_e$ for some $e$ , so $e \mapsto \Phi_e$ is a surjection from $\nat$ onto the partial computable functions, which are therefore countable (Proposition 3.3). The total computable functions form a subset, and the computable sets are the images of the computable characteristic functions under the bijection $X \mapsto \{ n : X(n) = 1 \}$ , so both are countable by Corollary 3.4. All three sets are infinite: they contain the constant functions, or the finite sets $\underline n$ .

Corollary 6.2.#

The set of functions $\nat \to \nat$ that are not computable, and the set of subsets of $\nat$ that are not computable, have the cardinality of the continuum.

Proof of Corollary 6.2.

They are the complements of countable sets in $\nat^\nat$ and $\cs$ , which have the cardinality of the continuum by Theorem 5.5. Conclude by Proposition 5.7.

The argument does not depend on the details of the model of computation. It uses only that every computable function has a finite description, so that there are countably many of them. For the same reason, there are only countably many subsets of $\nat$ definable by a formula of first-order arithmetic, so that most sets are not definable in arithmetic. The argument is not constructive: it does not exhibit any particular non-computable function.

6.2 Effective diagonalization

The diagonal function $g(n) = f_n(n) + 1$ of Example 4.5 is defined from the whole sequence $(f_n)$ . If this sequence is given by an algorithm, so is $g$ .

Definition 6.3.#

A sequence $(f_e)_{e \in \nat}$ of total functions $\nat \to \nat$ is uniformly computable if the function $(e, x) \mapsto f_e(x)$ is computable. A sequence of sets is uniformly computable if the sequence of their characteristic functions is.

Each function of a uniformly computable sequence is computable, but the converse fails: being uniformly computable means that a single algorithm computes $f_e(x)$ from $e$ and $x$ , not only that each $f_e$ has an algorithm of its own. For instance, let $f_e$ be the constant function with value $1$ if $e \in \emptyset'$ and $0$ otherwise, where $\emptyset'$ is the halting set of Corollary 6.8 below. Each $f_e$ is constant, hence computable, but $e \mapsto f_e(0)$ is the characteristic function of $\emptyset'$ , which is not computable.

Theorem 6.4.#

If $(f_e)$ is a uniformly computable sequence of total functions, then the function $g(n) = f_n(n) + 1$ is total computable and differs from every $f_e$ . Consequently, there is no uniformly computable sequence containing all total computable functions.

Proof of Theorem 6.4.

The function $g$ is obtained by composing the computable function $(e, x) \mapsto f_e(x)$ with $n \mapsto (n, n)$ and with the successor, so it is computable; it is total since each $f_e$ is. It differs from every $f_e$ by Proposition 4.3. If a uniformly computable sequence contained all total computable functions, it would contain $g$ .

The primitive recursive functions form a uniformly computable sequence $(f_e)$ : enumerate the derivations and evaluate them. This is the argument of Theorem 7.6 of “The Ackermann function”, which yields a total computable function that is not primitive recursive. The theorem shows that the total computable functions themselves cannot be enumerated in this way. The obstacle is identified by the following consequence.

Corollary 6.5.#

The set $\mathrm{Tot} = \{ e \in \nat : \Phi_e \text{ is total} \}$ is not computable.

Proof of Corollary 6.5.

The set $\mathrm{Tot}$ is infinite: the constant functions are total computable and pairwise distinct, and each of them is $\Phi_e$ for some $e$ . Suppose $\mathrm{Tot}$ computable. Then its principal function $p$ (Lemma 3.2) is computable, by

p(0) = \mu e\, [e \in \mathrm{Tot}], \qquad p(n+1) = \mu e\, [e > p(n) \wedge e \in \mathrm{Tot}],

where each search terminates since $\mathrm{Tot}$ is infinite. Let $f_n(x) = \Phi(p(n), x)$ . Since $\Phi$ is partial computable, $(n, x) \mapsto f_n(x)$ is partial computable; and it is total, since $p(n) \in \mathrm{Tot}$ . So $(f_n)$ is a uniformly computable sequence of total functions. Every total computable function is $\Phi_e$ for some $e \in \mathrm{Tot}$ , that is, $e = p(n)$ for some $n$ , so it is $f_n$ . This contradicts Theorem 6.4.

6.3 Partial functions

The enumeration $\Phi_0, \Phi_1, \dots$ of the partial computable functions is uniformly computable in the sense that $\Phi$ is partial computable. What happens when one diagonalizes against it?

Proposition 6.6.#

The partial function $d(e) \simeq \Phi_e(e) + 1$ is partial computable. If $c$ is a code of $d$ , that is, $d = \Phi_c$ , then $\Phi_c(c)\diverge$ .

Proof of Proposition 6.6.

$d$ is obtained by composing $\Phi$ , which is partial computable, with $e \mapsto (e, e)$ and with the successor; it is defined exactly when $\Phi_e(e)\converge$ . If $d = \Phi_c$ and $\Phi_c(c)\converge$ , then $\Phi_c(c) = d(c) = \Phi_c(c) + 1$ , which is impossible. So $\Phi_c(c)\diverge$ .

So the diagonal argument does not fail: it determines a point, $c$ , where the enumerated function $d = \Phi_c$ must be undefined. The partial functions escape diagonalization by being undefined at the diagonal point. This is why an enumeration of all partial computable functions can be computable, while an enumeration of all total computable functions cannot.

Theorem 6.7.#

The partial computable function $d(e) \simeq \Phi_e(e) + 1$ has no total computable extension: there is no total computable $h$ with $h(e) = d(e)$ whenever $d(e)\converge$ .

Proof of Theorem 6.7.

Suppose $h$ is such an extension, and let $c$ be a code of $h$ , so that $\Phi_c = h$ is total. Then $\Phi_c(c)\converge$ , so $d(c) = \Phi_c(c) + 1$ is defined, and $h(c) = d(c) = h(c) + 1$ , a contradiction.

Corollary 6.8.#

The halting set $\emptyset' = \{ e : \Phi_e(e)\converge \}$ is not computable.

Proof of Corollary 6.8.

If $\emptyset'$ were computable, the function $h$ defined by $h(e) = \Phi_e(e) + 1$ if $e \in \emptyset'$ , and $h(e) = 0$ otherwise, would be total computable: to compute $h(e)$ , decide whether $e \in \emptyset'$ , and run the computation of $\Phi_e(e)$ only if it halts. It would extend $d$ , contradicting Theorem 6.7.

This is the halting problem, which is the starting point of the course on fundamentals (Theorem 3.2 of “The halting problem”). Its proof there is the same diagonal argument, presented directly.

6.4 Diagonalization by requirements

In the diagonal argument, the sequence $Y$ is built to satisfy infinitely many conditions, $Y \neq X_n$ for each $n$ , each of which can be secured by fixing a single bit. Constructions in computability theory are usually organized in this way: one lists requirements $R_0, R_1, R_2, \dots$ , and builds the desired object by finite approximations, ensuring each requirement at its turn.

For strings $\sigma, \tau \in 2^{<\nat}$ , write $\sigma \preceq \tau$ if $\sigma$ is a prefix of $\tau$ , and $\sigma \prec X$ if $\sigma$ is a prefix of $X \in \cs$ . A requirement is a property of elements of $\cs$ , that is, a subset $R \subseteq \cs$ .

Lemma 6.9 (Finite extension).#

Let $(R_e)_{e \in \nat}$ be a sequence of requirements such that for every $e$ and every $\sigma \in 2^{<\nat}$ , there is $\tau \succeq \sigma$ such that every $X \succ \tau$ satisfies $R_e$ . Then there is $Y \in \cs$ satisfying every $R_e$ .

Proof of Lemma 6.9.

Fix an enumeration $\rho_0, \rho_1, \dots$ of $2^{<\nat}$ , given by Proposition 3.11. If $\tau$ is as in the hypothesis, so is every extension of $\tau$ ; in particular there is such a $\tau$ with $|\tau| > |\sigma|$ . Define $\sigma_0$ as the empty string and $\sigma_{e+1}$ as the first $\rho_i$ such that $\rho_i \succeq \sigma_e$ , $|\rho_i| > |\sigma_e|$ , and every $X \succ \rho_i$ satisfies $R_e$ . The strings $\sigma_0 \preceq \sigma_1 \preceq \cdots$ have strictly increasing lengths, so there is a unique $Y \in \cs$ with $\sigma_e \prec Y$ for every $e$ : its $n$ -th bit is the $n$ -th bit of any $\sigma_e$ of length greater than $n$ . Since $\sigma_{e+1} \prec Y$ , $Y$ satisfies $R_e$ .

Choosing $\sigma_{e+1}$ as the first suitable string in a fixed enumeration avoids any use of the axiom of choice, and makes the construction explicit.

Example 6.10.#

Let $(X_n)$ be a sequence in $\cs$ , and $R_n = \{ Y : Y \neq X_n \}$ . Given $\sigma$ , the string $\tau = \sigma \, i$ with $i = 1 - X_n(|\sigma|)$ satisfies the hypothesis: every $Y \succ \tau$ differs from $X_n$ at position $|\sigma|$ . This is the diagonal argument, except that the position at which $X_n$ is defeated is now chosen by the construction rather than fixed in advance.

Proposition 6.11.#

For every sequence $(X_n)$ in $\cs$ , there is $Y \in \cs$ that differs from every $X_n$ at infinitely many positions. If $(X_n)$ is uniformly computable, $Y$ can be taken computable.

Proof of Proposition 6.11.

For $e = \langle n, k \rangle$ , let $R_e$ be the requirement ” $Y(m) \neq X_n(m)$ for some $m \geq k$ ”. Given $\sigma$ , extend it by zeros to a string $\sigma'$ of length at least $k$ , and let $\tau = \sigma' i$ with $i = 1 - X_n(|\sigma'|)$ ; every $Y \succ \tau$ differs from $X_n$ at the position $|\sigma'| \geq k$ . By Lemma 6.9, some $Y$ satisfies all $R_{\langle n, k \rangle}$ , that is, differs from each $X_n$ beyond every $k$ .

If $(X_n)$ is uniformly computable, use the explicit extension above instead of a search in an enumeration: $\sigma_{e+1}$ is obtained from $\sigma_e$ by padding with zeros to length $\max(k, |\sigma_e|)$ and appending the bit $1 - X_n(\ell)$ , where $\ell = \max(k, |\sigma_e|)$ ; both steps are computable from $\sigma_e$ and $e = \langle n, k \rangle$ . Then $e \mapsto \sigma_e$ is computable, and so is $Y$ , since $Y(m)$ is the $m$ -th bit of $\sigma_{m+1}$ , which has length at least $m + 1$ .

The requirements of this proposition never interfere: once a requirement is satisfied, it remains satisfied whatever is done afterwards. Requirements of this kind can be handled one after the other, by finite extensions. The method was introduced by Kleene and Post to build Turing degrees with prescribed properties, and it is the elementary case of forcing. When requirements conflict, so that satisfying one may later injure another, one needs the priority method, which is the main technique of the theory of computably enumerable sets.

6.5 Exercises

Exercise 6.12 ★.

A function $h$ dominates a function $f$ if $h(n) \geq f(n)$ for all sufficiently large $n$ . Show that no total computable function dominates every total computable function.

Solution

If $h$ is total computable and dominates every total computable function, it dominates $h + 1$ , which is total computable: $h(n) \geq h(n) + 1$ for large $n$ , a contradiction.

Exercise 6.13 ★.

Show that there is no uniformly computable sequence $(X_n)$ of sets containing every computable set.

Solution

If $(X_n)$ is uniformly computable, then $Y(n) = 1 - X_n(n)$ is computable, as a composition of computable functions, and differs from every $X_n$ . Alternatively, apply Theorem 6.4 to the characteristic functions, replacing $f_n(n) + 1$ by $1 - f_n(n)$ .

Exercise 6.14 ★★.

Let $A = \{ e : \Phi_e(e)\converge = 0 \}$ and $B = \{ e : \Phi_e(e)\converge = 1 \}$ . Show that there is no computable set $S$ with $A \subseteq S$ and $S \cap B = \emptyset$ . (The sets $A$ and $B$ are computably inseparable.)

Solution

Let $S$ be computable, and let $c$ be a code of its characteristic function, so that $\Phi_c$ is total with values in $\{0, 1\}$ . If $c \in S$ , then $\Phi_c(c) = 1$ , so $c \in B$ , and $S \cap B \neq \emptyset$ . If $c \notin S$ , then $\Phi_c(c) = 0$ , so $c \in A$ , and $A \not\subseteq S$ . This is a diagonal argument in which the program $c$ is defeated at its own index.

Exercise 6.15 ★★.

Using Proposition 4.4 of “Computably enumerable sets” of the course on fundamentals, where computably enumerable sets are defined, show that $\mathrm{Tot}$ is not even computably enumerable.

Solution

$\mathrm{Tot}$ is infinite. If it were computably enumerable, there would be an injective total computable $f$ with $f(\nat) = \mathrm{Tot}$ . Then $f_n(x) = \Phi(f(n), x)$ defines a uniformly computable sequence of total functions containing every total computable function, contradicting Theorem 6.4. The proof of Corollary 6.5 is the special case where $f$ is the principal function.

Exercise 6.16 ★★★.

Show that there is a set $Y$ such that neither $Y$ nor its complement contains an infinite computable set.

Hint

For each infinite computable set $C$ , the requirement is: $C \not\subseteq Y$ and $C \not\subseteq \nat \setminus Y$ . Satisfy it by a finite extension.

Solution

The infinite computable sets form a countably infinite set, by Proposition 6.1 and Corollary 3.4 (it contains the sets $\nat \setminus \underline n$ ); let $C_0, C_1, \dots$ be an enumeration of them. Requirement $R_{2n}$ : $Y(m) = 0$ for some $m \in C_n$ ; requirement $R_{2n+1}$ : $Y(m) = 1$ for some $m \in C_n$ . Given $\sigma$ , since $C_n$ is infinite there is $m \in C_n$ with $m \geq |\sigma|$ ; extend $\sigma$ by zeros to length $m$ , then append the required bit. Every $Y$ extending the result satisfies the requirement. By Lemma 6.9, some $Y$ satisfies all requirements: each infinite computable set meets both $Y$ and its complement, so it is contained in neither. Such a set is called bi-immune.

6.6 Notes and references

The undecidability of the halting problem is due to Turing (1936), in the form that no machine decides whether a given machine is circle-free, that is, prints infinitely many digits. The finite extension method is due to Kleene and Post (1954), and the priority method to Friedberg and Muchnik (1956–1957). Rogers’ and Soare’s textbooks present diagonalization as the basic method of computability theory; Odifreddi gives a historical account of the many forms of the argument.

A. M. Turing, On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society (2) 42 (1936), 230–265.
S. C. Kleene and E. L. Post, The upper semi-lattice of degrees of recursive unsolvability, Annals of Mathematics 59 (1954), 379–407.
H. Rogers, Theory of Recursive Functions and Effective Computability, McGraw-Hill, 1967.
P. Odifreddi, Classical Recursion Theory, North-Holland, 1989.
R. I. Soare, Turing Computability: Theory and Applications, Springer, 2016.