bits.

FREE CONTRIBUTION CHRONOLOGY · 1931–1936

What can be computed?

Can every precisely stated problem be solved by a mechanical procedure?

The historical question

Several minimal formalisms captured the same class of effective procedures. By encoding procedures as data, they also made self-reference and the limits of procedure mathematically visible.

Formalization is powerful enough to define universal procedure and precise enough to prove that universal problem-solving is impossible.

Programs can become inputs

A universal interpreter accepts a description of another procedure and simulates its steps. That makes programs manipulable data, but it does not make every property of every program decidable. To see the distinction, suppose H(p,x) always terminates and correctly reports whether program p halts on input x. Define D(p) to loop forever when H(p,p) says halt, and to halt when H(p,p) says loop.

Ask what happens on D(D). If H predicts that it halts, D deliberately loops. If H predicts that it loops, D halts. Either answer contradicts the supposed specification of H. Therefore no such total, universally correct H exists for a sufficiently expressive computation model. This is a modern halting-problem presentation; Turing’s original circle-free-machine formulation requires care when reading the historical paper.

The result does not say that no individual program can be analyzed. A bounded loop may be easy to prove terminating. Nor does it say a practical analyzer is useless. An analyzer may be sound while returning unknown for some inputs, or may decide a restricted language. The impossible combination is unrestricted inputs, guaranteed termination, and universally correct yes-or-no answers for the stated property.

What the evidence does not establish

Parallel models and proofs matter. Resist collapsing Church, Post, Gödel, and Turing into one inevitable lone breakthrough.

Reconstruction exercise

Why does a tool that sometimes returns unknown avoid the contradiction? Give a restricted class of programs for which termination is easy to decide.

Worked solution

D relies on a definite yes-or-no answer from H for every input. Allowing unknown means the purported universal decision procedure no longer exists as specified. A language containing only finite straight-line arithmetic and fixed finite counted loops terminates under its defined operations; it has deliberately restricted expressiveness. Distinguish this restriction from claiming that arbitrary programs can be solved by waiting longer.

Test the limits and transfer the idea

1. Proof construction · allow 30 minutes

Put the hypothetical decider on the correct side of a reduction

Assume a total algorithm E(P) correctly decides whether unrestricted program P ever prints the exact marker DONE. Construct a wrapper W from an arbitrary program p and input x so that E(W) would decide whether p halts on x. State how the wrapper handles any output produced by p, and explain why an E that returns unknown on some programs no longer supplies the prohibited decider.

Get a starting hint

Simulate p silently and make printing DONE depend exactly on the event whose decidability is in question.

Compare your reasoning with the worked solution

Build W to simulate p on x while suppressing the simulated program's output. If and only if that simulation halts, W prints DONE and then halts. Thus E(W)=yes exactly when p halts on x. The transformation from p,x to W is effective and does not need to know whether p will halt. A total correct E would therefore decide unrestricted halting, contradicting its undecidability. Suppression matters: p might otherwise print DONE and continue forever, breaking the equivalence. If E can return unknown, the composed procedure also sometimes lacks a yes/no answer, so the contradiction does not follow. This is a modern reduction exercise; the original Turing paper's own formulation and proof should be read on their stated terms.

Check your reasoning

  • Builds an effective wrapper with both directions of the equivalence.
  • Handles output interference explicitly.
  • Identifies total yes/no completeness as the assumption lost with unknown.

2. Bound and proof · allow 30 minutes

A finite-state simulator does have a termination decision procedure

A deterministic closed toy machine has eight bits of mutable data and sixteen possible nonhalting control locations, with no external input or randomness. From any configuration it either halts or moves to one next configuration. Bound the number of nonhalting configurations and design a halting decision procedure. Explain why detecting a repeated configuration is conclusive here, and why this does not contradict unrestricted halting undecidability.

Get a starting hint

Include all mutable data and control state in the identity of a configuration.

Compare your reasoning with the worked solution

There are 2⁸×16=4096 possible nonhalting configurations. Simulate while storing visited configurations. Halt means yes; encountering a previously seen complete configuration means no, because determinism and no changing external input force the same future cycle. If the run has not halted, a repeat must occur by the 4097th observed nonhalting configuration. This is a decision procedure for the fixed finite model, though larger realistic state bounds may be impractical. Unrestricted computation permits unboundedly many reachable configurations across arbitrary memory use or input sizes, so this fixed finite bound does not supply a universal cutoff. Recording only the control location would be unsound because the data could differ and later enable termination.

Check your reasoning

  • Counts complete configurations as 4096.
  • Uses determinism and closed inputs to justify cycle detection.
  • Explains both the incomplete-state pitfall and the limited scope of the result.

Check your understanding

Which analyzer is ruled out by the diagonal argument?

  • One that proves some programs terminate
  • One that always terminates and correctly decides every unrestricted instance
  • One that sometimes reports unknown
Explanation

D relies on a definite yes-or-no answer from H for every input. Allowing unknown means the purported universal decision procedure no longer exists as specified. A language containing only finite straight-line arithmetic and fixed finite counted loops terminates under its defined operations; it has deliberately restricted expressiveness. Distinguish this restriction from claiming that arbitrary programs can be solved by waiting longer.

Sources and further reading