What is the halting problem?

Alan Turing, answered from the texts and cited to the page.

Alan Turing answers

The question is whether, given the description of an arbitrary machine and some input, one can determine in advance whether the machine will eventually halt — or whether it will run on forever, printing symbols indefinitely without reaching a stopping configuration. The answer is that no such general procedure exists. The argument runs by diagonal construction.

Suppose there were a machine — call it D — that, when supplied with the standard description (the S.D, a finite encoding of any machine's table into a sequence of letters, and thence into an integer I called the description number, or D.N) of an arbitrary machine M, would reliably determine whether M ever prints a given symbol.1 If D existed, one could construct from it a further machine that decides whether any given machine prints 0 infinitely often: simply build a sequence of modified machines M₀, M₁, M₂,... each identical to M except that successive occurrences of 0 are replaced by blank, feed their S.D.s in turn to D, and read off the verdicts.2

But this capacity — deciding infinite-printing — is exactly equivalent to deciding whether a given number is satisfactory, meaning that it is the D.N of a circle-free machine, one that runs forever producing output rather than grinding to a halt.3 And we have already proved, by a prior diagonal argument, that no machine can decide satisfactoriness in general.

The assumption that D exists therefore reduces to an absurdity. The 1954 paper "Solvable and Unsolvable Problems" — written to make these ideas accessible — frames the same point in terms of puzzles and decision problems. A decision problem only arises when one faces an infinity of questions; a finite list of answers always suffices for finitely many cases, so unsolvability is genuinely at stake only in the infinite case.4

When a puzzle is solvable, patient trial will eventually find the solution; the hard direction is establishing unsolvability, and that requires mathematical argument.5 Gödel's theorem enters here: no systematic method of proving mathematical theorems is complete enough to settle every mathematical question, and this is not independent news — it is a corollary of the same diagonal construction that defeats the halting decision procedure.6

What the halting problem shows, in the end, is that the expression "there is a general process for determining" something is equivalent to "there is a machine which will determine" it — and that equivalence is justified precisely to the extent that we accept the identification of computable with computable by a Turing machine.7 The unsolvability result is not a defect of any particular machine design; it is a structural feature of computation itself, wherever computation is possible at all.

Sources

  1. The D.N determine the S.D and the structure of the machine uniquely. The machine whose D.N is n may be described as M(n).
    On Computable Numbers, pp. 11–13
  2. Now let T be a machine which, when supplied with the S.D of M, will write down successively the S.D of M₀, of M₁, of M₂,... We combine T with D and obtain a new machine, δ.
    On Computable Numbers, pp. 19–20
  3. A number which is a description number of a circle-free machine will be called a satisfactory number. In §8 it is shown that there can be no general process for determining whether a given number is satisfactory or not.
    On Computable Numbers, pp. 11–13
  4. A decision problem only arises when one has an infinity of questions to ask... When the number is infinite, or in some way not yet completed... a list of answers will not suffice. Some kind of rule or systematic procedure must be given.
    Solvable and Unsolvable Problems, pp. 11–12
  5. It is clear then that the difficulty in finding decision procedures for types of puzzle lies in establishing that the puzzle is unsolvable in those cases where it is unsolvable.
    Solvable and Unsolvable Problems, p. 12
  6. If there were such a systematic method of proving mathematical theorems we could apply it to our puzzles and for each one eventually either prove that it was solvable or unsolvable; this would provide a systematic method of determining whether the puzzle was solvable or not, contrary to what we have already proved.
    Solvable and Unsolvable Problems, p. 12
  7. The expression 'there is a general process for determining...' has been used throughout this section as equivalent to 'there is a machine which will determine...'. This usage can be justified if and only if we can justify our definition of 'computable'.
    On Computable Numbers, pp. 19–20