On Computable Numbers, with an Application to the Entscheidungsproblem
A complete source map of Turing's 1936 paper, covering finite machine descriptions, configurations, a universal interpreter, diagonal undecidability, the analysis of effective calculation, and the Entscheidungsproblem application.
Turing's paper constructs a formal machine model from bounded local control plus an extendable symbolic tape, encodes each finite machine table as a standard description and description number, builds one machine that interprets those descriptions, and then uses self-application to prove that important behavior questions have no general mechanical decision procedure. It also distinguishes the formal machine definition from the informal claim that the model captures every effective calculation.
The archived file is a 36-page institutional facsimile from Stanford's CS103 archive, checked against the London Mathematical Society DOI record and the King's College Turing Digital Archive catalogue. It covers journal pages 230-265 and has SHA-256 a126650c315e998ba96ea8248a60bde0afe60fec3e810acfc2b6c70d3b0e9f36. Poppler and pypdf both report 36 pages; every page has a nonempty text layer. All 36 pages were read and rendered, and all 36 renders were inspected.
The conventional citation year is 1936, matching the paper header and reading date; the journal volume spans 1936-1937 and current publisher metadata labels first publication as 1937. The archived file does not include Turing's later three-page correction in Proceedings of the London Mathematical Society 43, 544-546. The correction repairs formal details in the Entscheidungsproblem proof and modifies the association between computable sequences and computable real numbers. Both parts were inspected separately and are outside GTK's reuse from the original paper.
Section map #
| Journal pages | Material | GTK use |
|---|---|---|
| 230-233 | Motivation, machines, configurations, circle-free sequences | Formal and historical foundation, translated into modern tuple/configuration notation |
| 233-239 | Example machines and abbreviated tables | Mechanism evidence; source-specific tables are not copied |
| 239-241 | Standard descriptions and description numbers | Primary basis for effective program encoding and programs-as-data |
| 241-246 | Universal computing machine | Primary basis for universal interpretation and step-simulation reasoning |
| 246-249 | Diagonal process, circle-freeness, specified-symbol printing | Primary undecidability boundary, with terminology kept historically precise |
| 249-254 | Extent of computable numbers and analysis of human calculation | Evidence that the informal scope claim is an argument from constrained effective procedure, not a formal equivalence theorem |
| 254-259 | Computable functions and closure examples | Background only; the recursive-functions chapter owns the modern function taxonomy |
| 259-263 | Application to the Entscheidungsproblem | Historical consequence; affected details are read with the published correction in mind |
| 263-265 | Appendix on lambda-definability | Preliminary equivalence argument; Turing's 1937 paper supplies the cleaner formal equivalence source |
Visual audit #
The paper's information-bearing visuals are typeset transition tables, complete-configuration traces, standard descriptions, description numbers, and long logical/lambda expressions. They are legible in the facsimile and were inspected at full page scale where they carry the argument. None is retained as an image: the notation is historical, dense, and less useful for the GTK chapter than independently constructed modern diagrams.
The GTK article preserves their explanatory roles through:
- a modern configuration/tape transition diagram;
- a two-stack interpreter invariant for simulating the tape;
- a universal-interpreter pipeline from encoded program and input to output or divergence;
- a memory-boundary ladder separating fixed devices, linear-bounded machines, and Turing machines.
Claims retained with scope #
- A finite transition table can be encoded as finite data and mechanically decoded.
- One universal machine can simulate the encoded steps of every machine in the model.
- No general machine decides Turing's circle-free property or whether an arbitrary machine ever prints a specified symbol.
- The proposed identification with all effective human calculation is not proved like a theorem between two formal systems.
- Formal equivalence with lambda-definability and general recursion should be cited to the dedicated 1937 equivalence paper, not inferred solely from the 1936 appendix.