The halting problem · Computability Theory

This lesson proves that the halting problem is not computable, and introduces the main tool for transferring undecidability from one problem to another: many-one reductions. With them, the undecidability of the halting problem propagates to many other questions about programs — halting on a fixed input, totality, emptiness of the domain — and, outside computability theory, to problems of number theory, group theory and logic.

3.1 The halting set

Definition 3.1.#

The halting set, or halting problem, is

\emptyset' = \{ e \in \nat : \Phi_e(e)\converge \}.

The set $H = \{ \langle e, x \rangle : \Phi_e(x)\converge \}$ is the general halting set.

The notation $\emptyset'$ , read “zero jump”, comes from the theory of the Turing jump: $\emptyset'$ is the jump of the empty set. The restriction to the diagonal $x = e$ makes the diagonal argument direct; the general halting set has the same degree of difficulty, as shown below.

Theorem 3.2.#

The set $\emptyset'$ is not computable.

Proof of Theorem 3.2.

Suppose $\emptyset'$ is computable. Consider the following algorithm $D$ : on input $x$ , decide whether $x \in \emptyset'$ ; if so, enter an infinite loop; otherwise, halt with output $0$ . By Proposition 1.6, $D$ computes a partial computable function, so it has an index $d$ , and for every $x$ ,

\Phi_d(x)\converge \iff x \notin \emptyset' \iff \Phi_x(x)\diverge.

For $x = d$ , this gives $\Phi_d(d)\converge \iff \Phi_d(d)\diverge$ , a contradiction.

This is Cantor’s diagonal argument applied to the table whose rows are the partial functions $\Phi_e$ : the algorithm $D$ differs from row $x$ at column $x$ , by converging where it diverges and diverging where it converges. The same argument is presented in the course on countability in a slightly different form, through partial functions without total extensions (Corollary 6.8 of “Diagonalization and computation”).

3.2 Many-one reductions

Definition 3.3.#

Let $A, B \subseteq \nat$ . A many-one reduction of $A$ to $B$ is a total computable function $f$ such that for all $x$ ,

x \in A \iff f(x) \in B.

We write $A \leq_m B$ if such an $f$ exists, and $A \equiv_m B$ if $A \leq_m B$ and $B \leq_m A$ .

The reduction transforms each question ” $x \in A$ ?” into a question ” $f(x) \in B$ ?” with the same answer. When $f$ is moreover injective, one speaks of a one-one reduction, written $A \leq_1 B$ .

Proposition 3.4.#

The relation $\leq_m$ is reflexive and transitive.
$A \leq_m B$ if and only if $\nat \setminus A \leq_m \nat \setminus B$ .
If $A \leq_m B$ and $B$ is computable, then $A$ is computable. Equivalently, if $A \leq_m B$ and $A$ is not computable, then $B$ is not computable.

Proof of Proposition 3.4.

The identity reduces $A$ to $A$ . If $f$ reduces $A$ to $B$ and $g$ reduces $B$ to $C$ , then $g \circ f$ is total computable and $x \in A \iff f(x) \in B \iff g(f(x)) \in C$ .
The same $f$ works: $x \notin A \iff f(x) \notin B$ .
$\chi_A = \chi_B \circ f$ is total computable.

To show that a set $B$ is not computable, it therefore suffices to reduce a non-computable set, typically $\emptyset'$ , to $B$ . Most reductions from $\emptyset'$ are built with the SMN theorem: from $e$ , one computes the index of a program whose behavior depends on whether $\Phi_e(e)$ converges.

Proposition 3.5.#

$\emptyset' \equiv_m H$ .
$\emptyset' \leq_m \{ e : \Phi_e(0)\converge \}$ , and $\emptyset' \leq_m \{ e : \mathrm{dom}(\Phi_e) \neq \emptyset \}$ .
$\emptyset' \leq_m \mathrm{Tot}$ and $\nat \setminus \emptyset' \leq_m \mathrm{Tot}$ , where $\mathrm{Tot} = \{ e : \Phi_e \text{ is total} \}$ .

In particular, none of these sets is computable.

Proof of Proposition 3.5.

$e \mapsto \langle e, e \rangle$ reduces $\emptyset'$ to $H$ . Conversely, let $z$ be the function of Example 2.4, with $\Phi_{z(e, x)}(y) \simeq \Phi_e(x)$ for all $y$ . Then $\langle e, x \rangle \in H \iff \Phi_e(x)\converge \iff \Phi_{z(e, x)}(z(e, x))\converge \iff z(e, x) \in \emptyset'$ , so $\langle e, x \rangle \mapsto z(e, x)$ reduces $H$ to $\emptyset'$ . (The function $n \mapsto z(\pi_0(n), \pi_1(n))$ is total computable, since the inverses $\pi_0, \pi_1$ of the pairing function are.)
With the same $z$ , the function $\Phi_{z(e, e)}$ is total if $e \in \emptyset'$ and nowhere defined otherwise. So $e \mapsto z(e, e)$ reduces $\emptyset'$ to both sets, and also to $\mathrm{Tot}$ , which proves the first half of item 3.
For the second half, let $g$ be total computable, given by Corollary 2.3, such that

\Phi_{g(e)}(x) \simeq \begin{cases} 0 & \text{if } \Phi_e(e)[x]\diverge,\\ \text{undefined} & \text{if } \Phi_e(e)[x]\converge. \end{cases}

This is a definition by cases with a computable condition (Proposition 1.4). If $e \notin \emptyset'$ , then $\Phi_e(e)[x]\diverge$ for every $x$ , and $\Phi_{g(e)}$ is total. If $e \in \emptyset'$ , then $\Phi_e(e)[x]\converge$ for all large $x$ , and $\Phi_{g(e)}$ is not total. So $g$ reduces $\nat \setminus \emptyset'$ to $\mathrm{Tot}$ .

The second half of item 3 is stronger than it looks. The lesson on computably enumerable sets shows that $\nat \setminus \emptyset'$ is not computably enumerable, and that sets reducible to a computably enumerable set are computably enumerable. Hence $\mathrm{Tot}$ is not computably enumerable; and by item 2 of Proposition 3.4, its complement is not either. Totality is strictly harder than halting, a fact made precise by the arithmetic hierarchy.

3.3 Undecidable problems in mathematics

Reductions from the halting problem show that many natural mathematical problems are undecidable. The following results are admitted; each is proved by coding computations into the problem considered.

The Entscheidungsproblem. The set of (codes of) valid formulas of first-order logic is not computable (Church, Turing, 1936). Later work showed that a language with a single binary relation symbol suffices.
The word problem for groups. There is a finitely presented group for which the set of words equal to the identity is not computable (Novikov, 1955; Boone, 1959).
Hilbert’s tenth problem. The set of polynomial equations with integer coefficients having a solution in integers is not computable (Matiyasevich, 1970, completing work of Davis, Putnam and Robinson). More precisely, every computably enumerable set (in the sense of the next lesson) is Diophantine, and therefore $\emptyset'$ reduces to the solvability of Diophantine equations.

3.4 Exercises

Exercise 3.6 ★.

Show that if $A$ is computable and $B \neq \emptyset$ , $B \neq \nat$ , then $A \leq_m B$ . What happens if $B = \emptyset$ or $B = \nat$ ?

Solution

Fix $b_1 \in B$ and $b_0 \notin B$ , and let $f(x) = b_1$ if $x \in A$ and $f(x) = b_0$ otherwise; $f$ is total computable and reduces $A$ to $B$ . If $B = \emptyset$ , then $A \leq_m B$ forces $A = \emptyset$ , since no $f(x)$ lies in $B$ ; similarly, $A \leq_m \nat$ forces $A = \nat$ .

Exercise 3.7 ★.

Show that $\{ e : \Phi_e(e)\converge = 0 \}$ is not computable.

Solution

Let $g$ be total computable with $\Phi_{g(e)}(y) \simeq 0$ if $\Phi_e(e)\converge$ , and undefined otherwise; it exists by Corollary 2.3, since the right-hand side is a partial computable function of $(e, y)$ . Then $e \in \emptyset' \iff \Phi_{g(e)}(g(e))\converge = 0$ , so $g$ reduces $\emptyset'$ to the set.

Exercise 3.8 ★★.#

Let $\mathrm{Inf} = \{ e : \mathrm{dom}(\Phi_e) \text{ is infinite} \}$ . Show that $\emptyset' \leq_m \mathrm{Inf}$ and $\nat \setminus \emptyset' \leq_m \mathrm{Inf}$ .

Solution

The reduction $e \mapsto z(e, e)$ of Proposition 3.5 sends $e \in \emptyset'$ to an index of a total function, whose domain is infinite, and $e \notin \emptyset'$ to an index of the nowhere defined function. The reduction $g$ of item 3 sends $e \notin \emptyset'$ to an index of a total function, and $e \in \emptyset'$ to an index of a function whose domain is $\{ x : \Phi_e(e)[x]\diverge \}$ , a finite initial segment of $\nat$ .

3.5 Notes and references

Turing proved in 1936 that no machine decides whether a given machine is circle-free, and deduced the unsolvability of the Entscheidungsproblem; Church obtained the latter independently with the λ-calculus. Many-one reducibility was introduced by Post in 1944, in the paper that founded the study of computably enumerable sets and their degrees. Davis’ survey and Matiyasevich’s book on Hilbert’s tenth problem, and Lyndon and Schupp’s book on combinatorial group theory, present the undecidability results listed above.

A. M. Turing, On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society (2) 42 (1936), 230–265.
A. Church, A note on the Entscheidungsproblem, Journal of Symbolic Logic 1 (1936), 40–41.
E. L. Post, Recursively enumerable sets of positive integers and their decision problems, Bulletin of the American Mathematical Society 50 (1944), 284–316.
M. Davis, Hilbert’s tenth problem is unsolvable, American Mathematical Monthly 80 (1973), 233–269.
Y. V. Matiyasevich, Hilbert’s Tenth Problem, MIT Press, 1993.
R. C. Lyndon and P. E. Schupp, Combinatorial Group Theory, Springer, 1977.