On Computable Numbers, with an Application to the Entscheidungsproblem

How to read the original

1. Begin with Computing machines and Definitions; distinguish finite control from the tape and distinguish circular from circle-free machines.
2. Trace one transition table before studying the universal-machine construction.
3. Read the undecidability argument and its application to the Entscheidungsproblem as separate logical steps; the modern halting proof below is a teaching reformulation.

What is being made precise

Turing replaces an informal instruction to calculate with a machine whose next action depends on a finite control state and one scanned symbol. The tape supplies extendable working storage. The paper primarily studies machines producing digits of computable numbers. Its circle-free terminology concerns producing infinitely many figure symbols; a circular machine can keep moving forever without producing more figures. Consequently, equating circular with halted misreads the original definitions. The familiar halting contradiction below teaches a related limit using modern terminology.

Build a small machine before reading universality

Consider an original teaching machine that increments a unary integer. Encode n as n consecutive marks followed by blank cells, with the head initially on the first mark or on blank when n=0. Its control state is scan. On a mark, it preserves the mark and moves right. On blank, it writes one mark and halts. For input three marks, four transitions produce four marks. The zero case writes one mark immediately.

State the invariant: every cell already passed contains an original mark, and no earlier cell has changed. The input contains finitely many marks, so the distance to the first blank decreases each time the scanning rule moves. The last transition extends the represented number by exactly one. This proof separates correctness from termination and exposes assumptions about the representation. A tape filled forever with marks is not a valid finite unary input under this contract.

A complete configuration consists of the tape contents, head position, and control state. A transition table alone is the program, while a configuration is one running instance. Encoding that table as a finite string lets a simulator receive programs as data. The simulator repeatedly decodes the current state and symbol, finds a rule, updates the represented tape, and continues. Universality concerns this ability to simulate, not an assertion that every simulation is fast or physically unbounded.

Follow the contradiction carefully

Assume a total procedure H(P,x) correctly decides whether program P halts on input x. Construct D(p) to loop forever when H(p,p) predicts halting, and to halt otherwise. Ask what D does on its own encoding. If H predicts halting, D loops; if H predicts nonhalting, D halts. Either answer violates the assumed contract. Therefore the universal total decider cannot exist.

The construction needs programs to have finite encodings and the alleged decision procedure to be usable as a subroutine. It does not require a machine to inspect a mystical property of itself. Its own description is simply a string supplied as input. Nor does the proof say that every termination question is difficult: the unary incrementer above has a short termination argument.

What to carry into programming

Execution for a million steps is evidence about a finite prefix, not proof of future behavior. A timeout is an operational limit. A termination checker that sometimes returns unknown can still be useful and sound. Restricting a language to bounded loops can make termination decidable while reducing expressiveness. These are choices of contract, not loopholes in the theorem.

Finally, the Entscheidungsproblem concerns a general decision method for first-order logical validity, not a method deciding every loosely described mathematical question. The historical paper connects a specific formal computation boundary to that logical problem. Keep the model, theorem, application, and broader interpretation distinct when explaining its significance.

Reconstruction exercise

Design a unary-decrement machine for finite nonempty strings of marks, starting at the leftmost mark. It should erase only the final mark and halt, representing zero as an empty tape. Specify how it finds the end, how it returns to the final mark, and which state distinguishes scanning from erasing. Trace inputs of length one and three. Give a correctness invariant and termination measure. Then explain why enumerating every input up to length one hundred does not replace your general proof, and why this terminating machine is compatible with undecidability of the general halting problem.

Worked solution

Use a scan state that moves right over marks. On the first blank, move left and enter an erase state. That state replaces the current mark with blank and halts. A one-mark input scans its mark, discovers blank, moves back, and erases the sole mark. A three-mark input follows the same steps after crossing three marks, leaving two. During scanning, the original marked prefix remains unchanged and the head advances toward its finite endpoint. Once blank is found, exactly one left move reaches the last mark because the input was required to be nonempty. The finite remaining marked suffix gives a decreasing measure for scanning; the final phase has a fixed number of steps. Bounded tests can expose table mistakes but cover only selected lengths. A proof for this restricted program says nothing about the existence of one total procedure that decides termination for every program and input.

Test the limits and transfer the idea

1. Reduction proof · allow 45 minutes

Relate halting to infinitely many printed figures

Turing's circular/circle-free distinction concerns producing finitely or infinitely many figure symbols, not simply stopping. Use a modern reformulation. Given an arbitrary program P and input x, construct a machine M that simulates P(x) one step at a time and prints one figure 0 after every simulated step that leaves P running. When the simulation halts, M enters an endless silent loop.

Analyze both possibilities for P(x). If a total procedure decided whether every such M prints infinitely many figures, show how it would decide halting. Explain the direction of the reduction, why M itself never needs to halt, and why constructing M does not require knowing whether P halts. State which part is a teaching reformulation rather than a literal reconstruction of the 1936 proof.

Get a starting hint

The construction is effective even though predicting its behavior is not. Its output productivity encodes the simulated termination property.

Compare your reasoning with the worked solution

If P(x) runs forever, M repeatedly completes another simulated step and prints another 0. It therefore produces infinitely many figures. If P(x) halts after finitely many steps, M prints only finitely many zeros and then silently loops forever. In both cases M can keep executing forever; continued execution alone does not distinguish the two output behaviors.

Suppose a total correct predicate C(M) returns true exactly when M prints infinitely many figures. Construct M from the finite code of P and data x, run C on its description, and answer that P halts exactly when C returns false. This would be a total halting decider, contradicting undecidability. Thus the hypothesized general productivity decider cannot exist. The reduction direction is from the halting decision problem to the productivity decision problem: a solution to the latter would solve the former, with the answer complemented.

Constructing M is a mechanical wrapper operation. It embeds the code/data and a simulator and does not precompute the infinite execution. If P is already halted initially, M simply enters its silent loop with zero printed figures, which is still finite. We assume a standard effective encoding and simulation model. This modern reduction illustrates why circular cannot be replaced with halted when reading the paper. It is not a claim that Turing's original machine notation or diagonal construction has exactly this source-code form.

Check your reasoning

• Correctly classifies both output histories while noting that M runs forever.
• Gives the total-decider contradiction with the right reduction direction.
• Explains effective construction and the historical/model distinction.

2. Algorithm and proof · allow 40 minutes

Build the decidable approximation and prove its limit

A student claims that testing every program for one million steps solves halting because real programs eventually either finish or get stuck. Define the bounded problem B(P,x,t): does P halt within at most t simulated steps? Give a terminating decision method and analyze its simulation cost at an abstract one-step level.

Then construct a program that defeats any fixed universal cutoff T while still halting. Explain how dovetailing can enumerate all halting program/input pairs without deciding every pair. Distinguish a sound 'unknown' result after a timeout from an incorrect 'does not halt' result, and connect the distinction to the paper's use of finite descriptions and universal simulation.

Get a starting hint

A finite run can certify an observed halt. A nonhalt claim concerns every later step.

Compare your reasoning with the worked solution

To decide B, inspect whether the starting configuration is halted, then simulate at most t transitions, accepting if a halted configuration appears and rejecting otherwise. A counter decreases from t to zero, so this meta-procedure terminates. It uses at most t simulated transitions; actual host-machine time can exceed O(t) if decoding, tape representation, or transition lookup has additional cost. A bounded decision is therefore possible without solving unbounded halting.

For any fixed T, a finite program can execute T+1 deliberate loop transitions before halting, or count beyond T in a representation whose execution requires more than T steps. A cutoff that interprets its uncompleted run as nonhalting is wrong on that program. Enlarging T only changes the counterexample; it does not establish a universal bound.

To enumerate halting pairs, effectively list their finite encodings. At stage s, simulate the first s pairs for s steps from their initial configurations, outputting any newly observed halting pair. A pair with enumeration index k and halting time h is eventually discovered at a stage at least max(k,h). Nonhalting pairs never appear, but no finite stage certifies their permanent absence. The process enumerates positive instances without deciding negative ones. A tool that reports unknown after the budget remains compatible with this limit and can still be useful. Universal simulation supplies a way to execute encoded programs; it does not supply a stopping oracle.

Check your reasoning

• Gives a terminating bounded algorithm with explicit initial-state and cost assumptions.
• Constructs a halting counterexample to every fixed cutoff.
• Explains dovetailing coverage and why missing output is not a negative decision.

Check your understanding

A simulator runs forever while printing no further figure symbols. In Turing’s original terminology, which classification applies?

• Circle-free because it keeps moving.
• Circular because it produces only finitely many figure symbols.
• Unclassifiable without physical memory limits.

Explanation

The original distinction concerns continued production of figure symbols, not merely continued movement.

A tool proves termination for bounded loops but returns unknown on some recursive inputs. Does the halting theorem rule it out?

• Yes, every termination proof is impossible.
• Yes, if it accepts source code as input.
• No, it does not promise a total yes/no answer for every program.

Explanation

The impossible contract combines unrestricted coverage, total termination, and universally correct yes/no answers.

Original paper and sources

Alan M. Turing. On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, second series, volume 42. Received 28 May 1936; journal publication 1937. Linked copy includes the original paper.

Read the original paper →

Read the primary paper: University of Virginia

• On Computable Numbers, with an Application to the Entscheidungsproblem: University of Virginia