V.20 The Insolubility of the Halting Problem

What does it mean to understand a certain area of mathematics completely? One possible answer is that you understand it when you can solve its problems mechanically. Consider, for instance, the following question. Jim is half the age of his mother, and in twelve years’ time he will be three-fifths of her age. How old is his mother now? For a child who is just old enough to understand the concept of “three-fifths,” this is likely to be an impossibly difficult problem. A bright and slightly older child may be able to solve it after some hard thought, which will probably include a certain amount of trial and error. But for anybody who has learned how to translate such problems into equations and who knows how to solve two simultaneous linear equations, the problem is utterly routine: let x be Jim’s age and y his mother’s; then the problem tells us that 2x = y and 5(x + 12) = 3(y + 12); the second equation can be rearranged to give 3y - 5x = 24; substituting y = 2x gives x = 24, so y = 48.

The more mathematics one learns, the more one finds that problems that once seemed to be difficult and to require ingenuity have become routine in this sort of way, and it is eventually tempting to ask whether all of mathematics might, ultimately, be reducible to a mechanical procedure. And even if you think that that is a bit much to hope for, you can still ask the question about certain natural classes of problems, such as simultaneous linear equations. Perhaps there is always a mechanical procedure for solving the problems in any sufficiently “natural” class, even if there is not necessarily a systematic way of finding the mechanical procedure.

One class of problems that has been intensively studied for several centuries is that of Diophcrntine equations, which are equations in one or more variables where one stipulates that the solutions should be integers. The most famous Diophantine equation is the Fermat equation xⁿ + yⁿ = zⁿ, but this is somewhat complicated because one of the variables, n, appears as an exponent. Suppose we restrict attention to polynomial equations, such as x² - xy + y² = 157. Is there a systematic way of telling whether such an equation has integer solutions?

The left-hand side of the equation x² - xy+y² = 157 is equal to (x² + y² + (x - y)²)/2. Therefore, any solution (x,y) must satisfy x² + y² ≤ 314, which makes it a short task to search through all possibilities until one discovers the solution x = 12 and y = 13 (or vice versa). However, an exhaustive search is not always possible: consider, for example, the equation 2x² - y² = 1. This is a special case of the Pell equation, discussed in ALGEBRAIC NUMBERS [IV.1 §1]. The Pell equation can be solved systematically, with the help of CONTINUED FRACTIONS [III.22], and this leads to a systematic solution of all polynomial equations of degree up to 2 in two variables.

By the end of the nineteenth century, these and many other Diophantine equations had been completely solved, but there was no single overarching method that dealt with all of them. This state of affairs prompted HILBERT [VI.63] to include, as the tenth in his famous list of twenty-three unsolved problems, the question of whether there was a single, universal procedure for solving all polynomial Diophantine equations in any number of variables. Later, in 1928, he asked the more general question alluded to earlier: is there a universal procedure for determining the truth or falsity of any mathematical statement? This question became known as the Entscheidungsproblem (which means “decision problem” in German).

Hilbert expected, or at least hoped, that the answers to both questions would be yes. In other words, he hoped that the mathematicians of his day were in the position of the child who has not yet learned how to solve simultaneous equations. Perhaps a new age was dawning in which it would be possible, at least in principle, to solve all mathematical problems systematically and without relying on native wit.

The evidence in favor of such a view was not very strong: although problems of some kinds could be solved fully systematically, others, including Diophantine equations, stubbornly resisted, and the role of ingenuity in mathematical research appeared to be as important as ever. But if one wanted to give a negative answer to Hilbert’s questions, then one faced a major challenge: in order to prove rigorously that there is no systematic procedure for accomplishing a particular task, one has to be absolutely clear about what a “systematic procedure” actually is.

Nowadays there is an easy answer to this: a systematic procedure is anything that you can program a computer to do. (Strictly speaking, this is an oversimplification, because one also makes the idealizing assumption that the computer has unlimited storage space.) Our feeling that we do not have to think too hard to solve simultaneous equations is reflected in the fact that we can devise a computer program to do it for us (though if we want the program to be fast and numerically robust, we will face very interesting problems: see NUMERICAL ANALYSIS [IV.21 §4]). However, Hilbert asked the questions before computers existed, so it was a remarkable achievement when in 1936 CHURCH [VI.89] and TURING [VI.94] independently managed to formalize the notion of what we now call an ALGORITHM [IV.20 §1]. That is, they each gave a precise definition of the notion of an algorithm. Their definitions were quite different, but later shown to be equivalent, which means that anything that can be done by an algorithm in Church’s sense can be done by an algorithm in Turing’s sense, and vice versa. Turing’s formalization, which had a big influence on the design of modern computers, is discussed in COMPUTATIONAL COMPLEXITY [IV.20 §1.1], while Church’s is described in ALGORITHMS [II.4 §3.2], but for the purposes of this article we shall use the anachronistic definition with which this paragraph began.

It turns out that once one has any sufficiently precise notion of “algorithm,” one is just a few short steps away from a negative answer to Hilbert’s Entscheidungsproblem. To see this, imagine that L is some programming language (such as Pascal or C++). Given any string of symbols, we can ask of it the following question: if I present that string of symbols to my computer as a program in L, will the program run forever, or will it eventually stop? This is called the halting problem. (Note that the word “problem” really means “class of problems.”) The halting problem may not seem very mathematical, but certain instances of it certainly are. For example, suppose that after a quick look at a program you realize that it does the following. In one portion of the memory it stores an even number n, which at the beginning is set to 6. It then checks for every odd number m less than n whether m and n - m are both prime. If the answer is yes for some m, then it adds 2 to n and repeats. If the answer is no for all m, then it halts. This program will halt if and only if the GOLDBACH CONJECTURE [V.27] is false.

Turing proved that there is no systematic procedure for solving the halting problem. (Church proved an analogous result for his notion of recursive functions.) Let us see how Turing’s argument works for the language L. In this case, it shows that there is no systematic procedure for recognizing which strings of symbols form programs in L that halt, and which do not. The proof is a reductio ad absurdum, so we begin by assuming that there is such a procedure. Let us call it P. Suppose that L is like most computer languages, in that a typical program asks for an input, which affects its subsequent behavior. Then P will be able to tell, given any pair of strings (S,I), whether S is a program in L that halts if the input is I.

Now let us create a new procedure Q out of P. Given any string S, we start by getting Q to run P on the pair (S,S). If P judges that S does not halt when presented with itself as input, we then cause Q to halt. But if P judges that S does halt when presented with itself as input, then we artificially send Q into an endless loop, so that it does not halt. (If S is not a valid program in L, then let us say that Q halts—it does not really matter though.) To summarize, if S halts for input S, then Q does not halt for S, and if S does not halt for S, then Q does halt for S.

But now let us suppose that S is the program for Q itself. Does Q halt with input S? If it does, then S halts with input S, so Q does not halt. If it does not, then S does not halt with input S, so Q does halt. This is a contradiction, and therefore the procedure P out of which Q was built could not have existed.

That solves the general version of Hilbert’s problem: there is no algorithm that will determine the truth or falsity of arbitrary mathematical statements. But it does so by constructing, for any given algorithm, a rather artificial statement. We do not yet have an answer to the question of what happens if we look at more specific and more natural classes of statements, such as that a given Diophantine equation has a solution.

Remarkably, however, specific questions of this kind can often be shown to be equivalent to the general question, by a technique known as encoding. For example, there is no algorithm that will take as its input a set of polygonal tiles (suitably represented) and tell you whether it is possible to tile the plane using copies of just those tiles. How do we know this? Well, given any algorithm, there is a clever way of devising a set of tiles (this is the encoding) that will tile the plane if and only if the algorithm fails to halt. Therefore, if there were an algorithm for determining whether the tiles could tile the plane, then there would be an algorithm for solving the halting problem—but there is not.

Another famous example of a more specific problem for which there is no algorithm is the word problem for groups. Here you are given a set of generators and relations for a group and asked whether the group is trivial—that is, whether it contains just the identity. Again, an algorithm that could decide this would give us an algorithm that could solve the halting problem, so there cannot be one. The encoding process used to prove this is much more difficult than it is for tiling the plane: the insolubility of the word problem for groups is a famous theorem proved by Pyotr Novikov in 1952. For a much fuller explanation of this problem and its solution, see GEOMETRIC AND COMBINATORIAL GROUP THEORY [IV.10].

Finally, what about Hilbert’s tenth problem? This has become another famous and very hard theorem, due to Yuri Matiyasevitch in 1970, who built on work of Martin Davis, Hilary Putnam, and Julia Robinson. Matiyasevitch managed to produce a system of ten equations, involving two parameters m and n, that could be solved in integers if and only if m was the 2nth Fibonacci number. From Robinson’s work it followed that, given any algorithm with integer inputs, there was a system of Diophantine equations, involving a parameter q, that could be solved if and only if the algorithm halted at q. That is, any instance of the halting problem can be encoded as a system of Diophantine equations, so there is no general algorithm for deciding whether Diophantine equations can be solved.

Different people draw different morals from these results. In the opinion of some mathematicians, they show that there will always be a place for human creativity in mathematics, however powerful the computers of the future might be. Others maintain that although we now know that we cannot systematically solve all problems in mathematics, the effect on most mathematics is very slight: one should be aware that certain kinds of problems are sometimes equivalent to the halting problem, and that is it. Still others point out that it is often easy to devise an algorithm to solve a problem but much harder to make it efficient. This issue is discussed in great detail in COMPUTATIONAL COMPLEXITY [IV.20].

Turing’s argument for the insolubility of the halting problem is closely related to GÖDEL’S THEOREM [V.15], and both proofs use diagonal arguments, which are discussed in COUNTABLE AND UNCOUNTABLE SETS [III.11].