# Turing 1936 — On Computable Numbers

slug: turing-1936 · https://miscsubjects.com/a/turing-1936 · tags: source, grain, convergence, turing · updated 2026-07-17T02:43:21.168Z

## The Source

Turing, A.M. (1936). "On Computable Numbers, with an Application to the Entscheidungsproblem." *Proceedings of the London Mathematical Society*, Series 2, Vol. 42, pp. 230-265. DOI: 10.1112/plms/s2-42.1.230.

## The Claim

Some problems cannot be solved by any mechanical procedure. [SOURCE:turing-1936|type:mathematical] Turing proved this by inventing a machine that defines what "mechanical" means.

## The Context

Hilbert asked for a decision procedure. He wanted a single algorithm that could settle every mathematical question. Mathematicians believed such a procedure existed. They were wrong. Turing was twenty-four. He solved the problem by imagining a machine.

The year was 1936. Europe was darkening. Gödel had already shattered completeness in 1931. [SOURCE:godel-1931|type:mathematical] The foundations of mathematics were in crisis. Hilbert's program was the last hope: a mechanical procedure to decide all truths. Turing ended that hope with a thought experiment.

## The Evidence

Turing defined a computable number as one whose decimal digits a machine could print. The machine reads a tape. It moves left or right. It writes symbols or erases them. Its behavior is determined by a finite table of instructions. This is the Turing machine. [SOURCE:turing-1936|type:mathematical]

Turing then constructed a universal machine. One machine that can simulate any other. Feed it the description of any Turing machine and its input. It computes what that machine would compute. [SOURCE:turing-1936|type:mathematical]

Then he proved the halting problem. No machine can predict whether another machine will halt or run forever. The proof is a diagonal argument. The machine is asked to judge itself. Contradiction follows. Therefore no such machine exists. [SOURCE:turing-1936|type:mathematical]

The Entscheidungsproblem falls immediately. If you cannot determine whether a machine halts, you cannot determine whether a theorem is provable. The limit is absolute.

## The Convergence

This source instantiates **C20 — Universal Computation**. [SOURCE:turing-1936|type:mathematical]

Turing's machine is the abstract structure that underlies every computer. One machine simulates all others. This is not metaphor. It is theorem.

The paper also instantiates **C08 — Recursion / Self-Reference**. [SOURCE:turing-1936|type:mathematical] The diagonal argument requires a machine to examine its own behavior. Self-reference produces undecidability.

The convergence is triple. Church proved the same result independently, using lambda calculus. [SOURCE:church-1936|type:mathematical] Post arrived independently with finite combinatory processes. Three methods, one limit. The boundary of computation is real.

## The Honest Limits

Turing assumed a discrete, deterministic machine. Nature is not discrete. Quantum mechanics is probabilistic. Whether the universe itself is computable remains open. [SOURCE:turing-1936|type:theoretical]

Turing did not address computational complexity. A problem can be computable yet take longer than the age of the universe to solve. P versus NP was decades away.

His machine has infinite tape. Real machines have finite memory. The idealization matters for some proofs.

The Church-Turing thesis is a hypothesis about physics, not a theorem. It may fail at quantum or biological scales. [SOURCE:turing-1936|type:theoretical]

## The Receipt

"We may compare a man in the process of computing a real number to a machine which is only capable of a finite number of conditions... The machine is supplied with a 'tape' (the analogue of paper) running through it, and divided into sections (called 'squares') each capable of bearing a 'symbol'."

This is §1 of the paper. Turing constructs the machine from scratch.

The diagonal argument, in his own words:

"It follows that there can be no machine E which, when supplied with the S.D [standard description] of any computing machine M, will determine whether M ever prints a given symbol..."

The machine D, applied to itself, produces a contradiction. Therefore D cannot exist. The receipt is complete. [SOURCE:turing-1936|type:mathematical]

## Related Sources

- [SOURCE:church-1936|type:mathematical] — Alonzo Church proved the same undecidability independently via lambda calculus
- [SOURCE:godel-1931|type:mathematical] — Gödel's incompleteness theorems set the stage for Turing's limit
- [SOURCE:post-1936|type:mathematical] — Emil Post arrived independently with finite combinatory processes
- [SOURCE:von-neumann-1945|type:empirical] — Von Neumann built the stored-program computer architecture from Turing's blueprint
- [SOURCE:shannon-1948|type:theoretical] — Shannon's information theory completes the triad: computable, communicable, compressible
- [SOURCE:prigogine-1977|type:empirical] — Dissipative structures push against the same limits: what can be computed versus what can exist

## Sources

1. On Computable Numbers, with an Application to the Entscheidungsproblem — https://doi.org/10.1112/plms/s2-42.1.230
2. Gödel's Incompleteness Theorems (1931)
3. Church's Proof via Lambda Calculus (1936)
4. Post's Finite Combinatory Processes (1936)