Works › On Computable Numbers, with an Application to the Entscheidungsproblem
Work #1547 · Early period

On Computable Numbers, with an Application to the Entscheidungsproblem

Turing's 1936 founding paper — the Turing Machine and the undecidability of the halting problem

Alan Turing · 1936 · English · Mathematical-logical paper

Tradition: Mathematical logic / computability theory / Cambridge analytic-mathematical philosophy

Turing's 1936 founding paper of computer science — the Turing Machine and the undecidability of the Entscheidungsproblem

Published in the Proceedings of the London Mathematical Society in 1936-37 (Series 2, vol. 42, pp. 230-265, with a correction at pp. 544-546), 'On Computable Numbers, with an Application to the Entscheidungsproblem' is the founding paper of theoretical computer science. Turing — then a 23-year-old Cambridge fellow — introduces the abstract 'a-machine' (later 'Turing Machine'), a finite-state device with a read-write head moving over an infinite tape of symbols. He defines computable real numbers as those whose decimal expansions can be produced by such a machine, proves the existence of a Universal Turing Machine (one machine that can simulate any other machine when given its description as input), demonstrates the undecidability of the halting problem (no machine can decide, for an arbitrary machine M and input I, whether M halts on I), and concludes that Hilbert's Entscheidungsproblem — the question of whether there is a decision procedure for first-order logic — is unsolvable. The paper appeared independently of Alonzo Church's 1936 lambda-calculus proof of the same conclusion (Turing and Church met in Princeton later that year, and Turing's PhD under Church appeared as 'Systems of Logic Based on Ordinals', 1938). Together the Turing-Church results established the Church-Turing thesis: the intuitive concept of effective calculability coincides with the formal concepts of recursion, lambda-definability, and Turing-computability.

Author

Editions cited

  • On Computable Numbers, Proceedings of the London Mathematical Society, ser. 2, vol. 42 (1936-37), 230-265; correction at vol. 43 (1937), 544-546
  • Reprinted in Martin Davis, ed., The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions (Raven Press, 1965)
  • In Turing, Collected Works: Mathematical Logic, ed. R. O. Gandy and C. E. M. Yates (Elsevier, 2001)
  • Critical commentary: Charles Petzold, The Annotated Turing (Wiley, 2008); Robin Gandy, 'The Confluence of Ideas in 1936' in The Universal Turing Machine: A Half-Century Survey (Oxford, 1988)
Compare this work

School Embodiments

Logicism · 35%
Analytic Metaphysics / Logical Atomism · 14%
Naturalism · 11%
Structuralism · 10%
Realism · 10%
Analytic Philosophy · 8%
Logicism 35%

Founding paper of computability theory and theoretical computer science.

"A number is computable if its decimal can be written down by a machine." (On Computable Numbers, §1)
Analytic Metaphysics / Logical Atomism 14%

Foundational paper for the analytic philosophy of computation.

"Every computable function can be computed by a universal machine." (On Computable Numbers, §6)
Naturalism 11%

Naturalistic-mathematical framework.

"The machine is a deliberately abstract idealisation of the activity of a human computer." (On Computable Numbers, §9)
Structuralism 10%

Structural account of computation.

"All computation reduces to the structural manipulation of symbols on tape." (On Computable Numbers, §1)
Realism 10%

Mathematical realism about computable functions.

"Computable functions are a definite mathematical class." (On Computable Numbers, §1)
Analytic Philosophy 8%

Analytic-philosophical tradition.

Internal Tensions

The founding paper of theoretical computer science and one of the most-cited mathematical papers of the twentieth century. Together with Church's contemporaneous lambda-calculus paper, established the Church-Turing thesis. Turing's wartime cryptanalytic work at Bletchley Park (Enigma, Tunny) used these abstract ideas in practical machine design; modern computer architectures remain Turing-machine-equivalent.

⧖

I. Time

1936 (paper read May, published November). Twenty-three-year-old Turing, then fellow of King's College, Cambridge.

Attributes
Extent: Infinite Ontological Status: Substantival Grain: Discrete Freedom: Deterministic Traversability: Linear Direction: Uni-directional Dimensionality: One
✦

II. Space

Cambridge / Princeton. Turing's intellectual context was Newman's logic course at Cambridge and the contemporary Princeton group (Church, Kleene, Rosser).

Attributes
Extent: Infinite Ontological Status: Substantival Curvature: Flat Dimensionality: Three Locality: Local
◉

III. Matter

Single 36-page mathematical paper. The abstract Turing Machine is the paper's distinctive contribution — a machine of pure mathematical-symbolic operation, with no physical instantiation required.

Attributes
Extent: Infinite Ontological Status: Substantival Conservation: Conserved Dimensionality: Three Locality: Local
◎

IV. Observer

Early Turing as logician-mathematician. The paper's 'computer' (originally a human following definite rules) is the abstract idealisation that Turing then mechanises.

Attributes
Time Instance: Single Space Instance: Single Knowledge Extent: Mediated Knowledge Retainment: Partial Physicality: Embodied Agency: Active Number: Plural Metaphysical Agency: Impersonal
⚡

V. Energy

Founding-logical energies of the 1936 'three-miracle' year (Turing, Church, Post all independently characterised effective calculability).

Attributes
Extent: Infinite Ontological Status: Substantival Conservation: Conserved Dispersibility: Irreversible
⧉

VI. Information

The founding paper of theoretical computer science and of the formal theory of information processing. Every digital computer is in principle a Turing machine.

Attributes
Ontological Status: Substantival Cosmic Conservation: Conserved Personal Conservation: Non-conserved Granularity: Discrete

Personas that cite this work

Alan Turing Kurt Gödel John Archibald Wheeler David Deutsch

Personas with the nearest attribute fingerprint

Historical figures whose own classification on the same six-dimensional grid lands closest to this work's. Computed by attribute-agreement on coordinates both address.

97%
Alan Turing
33/34
97%
Thales of Miletus
28/29
93%
Anaximander of Miletus
28/30
91%
David Lewis
31/34
91%
Democritus of Abdera
31/34
91%
Peter Singer
31/34

Computed school proximity

The work's attribute fingerprint scored against all schools using the same quiz scorer. Useful as a sanity check on the hand-curated embodiments above.

74%
Cognitivism (Mind)
23/26
71%
Mechanism
22/26
69%
Deism
23/26
69%
Philosophy of Science
23/26
69%
Analytic Philosophy
23/26
67%
Modal Realism
22/26
66%
Legalism (Fa-jia)
22/26
66%
Materialism (Philosophical)
21/26

How On Computable Numbers, with an Application to the Entscheidungsproblem resolves each dilemma

34 resolved positions across 4 dimensions, including 6 distinctive where the majority of schools go the other way · 23 unaligned.

Each dimension is sorted so minority positions come first. Mainstream positions are folded into an expandable list.

Time · 9 dilemmas · 5 distinctive

Persistence, the future, and the direction of becoming.

Distinctive · only 9% of schools agree (18/202)
Do you really choose?
If the brain is a physical system and physical systems are governed by laws, then every choice is also a chain of causes — which raises the question of what was really left to choose.
Choice is real within a determined order — agency and determinism aren’t opposites.
On this view, the future is determined and you are genuinely choosing. Those aren't contradictory because the determination runs through you rather than around you: your reasoning, deliberation, and assent are the way the determined outcome gets settled. Choice is what it feels like from …
Roads not taken The future is open and you are a genuine origin of it. (69%) · Choice is structural illusion — every event is fixed by the prior state. (10%) · Even if the universe is undetermined, you are not the chooser. (6%)
Distinctive · only 9% of schools agree (18/202)
Are addicts responsible for their addiction?
Addiction looks from one angle like the textbook case of agency failing — a person doing what they don't, in any meaningful sense, want to do. From another angle it looks like agency at work in hard conditions. Which it is depends on what agency is.
The addict is genuinely responsible within a determined order.
On this view, the addict is acting within a determined order but is genuinely acting — making decisions, endorsing or resisting urges, seeking or refusing help. Responsibility attaches not because some uncaused choice happened, but because the addict is the kind of agent through which …
Roads not taken The addict could have chosen otherwise — that's why recovery is real. (69%) · The addict's behaviour is the outcome of causes; 'responsibility' is a useful fiction, not a metaphysical fact. (10%) · Even if the universe is undetermined, the addict isn't the chooser. (6%)
Distinctive · only 9% of schools agree (18/202)
Should we hold AI systems responsible for what they do?
When an autonomous AI takes an action that harms someone, the question of who or what is responsible — the developer, the operator, the model itself — turns on whether the model is the kind of thing that can be a responsible agent.
The AI can be a genuine agent within determined conditions — and therefore genuinely responsible.
On this view, what makes a being responsible is not indeterminism but the kind of process the being is. An AI that deliberates, considers consequences, can be given reasons, and modifies its behaviour on reflection is doing what responsible agency is, even if its underlying …
Roads not taken An AI without a free will is not the kind of thing that can be responsible. (69%) · An AI's behaviour is fully determined by training and input; 'responsibility' applies if at all to its makers. (10%) · Neither AIs nor anyone else are the locus of free agency; the question is the wrong one. (6%)
Distinctive · only 15% of schools agree (31/202)
Is the universe running out of usable energy?
The heat death of the universe — entropy maxed out, no further work possible — is among the more sobering implications of mainstream physics. Whether it is structurally inescapable depends on what kind of finitude the cosmos has.
Both time and matter are unbounded; 'running out' is misframed.
On this view, the cosmos has neither a temporal horizon nor a material exhaustion point. The framing of running out presupposes bounds that the cosmos doesn't have. Energy gradients perpetuate; new configurations emerge; the categories that make heat-death scary don't apply at the cosmic scale.
Roads not taken Time is unbounded but matter is finite; usable energy can fail without time failing. (47%) · Time both has and lacks bounds depending on the level you ask at; finitude is conventional. (26%) · The cosmos has bounds; heat death is a real horizon. (12%)
Distinctive · only 15% of schools agree (31/202)
Are natural resources fundamentally finite, or only practically so?
Whether we can grow our way out of resource constraints — or whether the cosmos sets limits the economy ultimately must obey — depends on what kind of finitude matter has.
Resources are practically inexhaustible on cosmic scales; terrestrial limits are engineering.
On this view, matter and time are both unbounded at the largest scales. Terrestrial resource limits are real engineering and political constraints but not metaphysical ones; the cosmos can in principle support whatever expansion intelligence is capable of.
Roads not taken Time goes on but matter is bounded; we are eventually constrained even with infinite time. (47%) · The finitude question is level-dependent; resource ethics happens at the level that constrains us. (26%) · Resources are finite in the strict sense; living well requires accepting the limit. (12%)
4 mainstream positions
Could we owe future generations more than is materially possible to provide? Both time and matter are unbounded; we cannot in principle owe more than is possible. 15% How much weight do future people deserve? Future people are as real as you are — and their interests count for as much. 47% Is regret rational? The past is as real as the present; regret is a real attitude toward a real thing. 47% Do we owe extinct species something we cannot give them? Extinct species are as real as we are; they have standing. 47%
Matter · 7 dilemmas, all mainstream
Is the world created from nothing? Yes — matter was created and is conserved as a real substance. 55% Is the physical world fully real? Yes — the physical world is fully real, mind-independent, persisting. 55% Does matter have intrinsic moral standing? Matter is morally considerable insofar as it is created or conserved good. 55% What is money? Money is a real institution with intrinsic features. 54% What is a nation? A nation is a real moral community with intrinsic character. 54% What makes someone male or female? Sex is a real biological kind with given content. 54% Should we edit the human germline? Human nature is a real biological kind given by reproductive biology or by creation; editing the germline transgresses what is given. 54%
Observer · 37 dilemmas, all mainstream
Could causation work backwards? Causation runs one way — the arrow of time is real and structural. 68% Is the asymmetry between memory and anticipation a real feature of time, or just of us? The asymmetry is real because time itself has a real direction. 68% Is the arrow of time a real feature of the cosmos, or only of how we describe it? The arrow is real and structural; the asymmetry isn't an artifact of description. 68% Is environmental damage ever truly permanent? Damage is real and permanent on the relevant timescales. There is no recovery; there is only limitation. 66% Can a civilization recover from collapse? Civilizational complexity is hard to build and easy to lose; recovery is at best partial. 66% Does the second law of thermodynamics mean something morally? Entropy is what time is. The moral weight, if any, is the weight of working against the current. 66% When does a person begin? A person exists from conception — when a new being comes into existence. 54% What is marriage? Marriage has a given form — it’s a kind of thing we recognize, not make. 54% What is our place in nature? Active in a real nature — we cultivate, steward, transform. 48% Should we colonize space? Cultivating worlds beyond Earth is the next form of stewardship. 48% Is genetic engineering of food stewardship or domination? Genetic modification is cultivation by other means. 48% Should we trust expert testimony when we can't verify it? Trust expertise whose conclusions a competent mind can in principle reproduce. 32% Is religious revelation a real source of knowledge? Revelation is evaluable by reason — and not above it. 32% Does an LLM 'know' the things it correctly produces? An LLM can produce correct outputs but not reason to them; useful, not knowing. 32% Are coincidences ever more than coincidence? — — Are the dead morally present to the living? — — Are there indivisible units of experience? — — Can prayer for someone far away affect them? — — Could a fetal brain organoid in a petri dish be conscious? — — Could an AI have a mind that matters? — — Do animals have moral standing comparable to humans? — — Does environmental harm in another country bind me morally? — — Does history have a direction or meaning? — — Does meditation reveal something genuinely timeless? — — Does prayer change God's mind? — — How is knowledge of reality produced? — — If a teleporter copied and destroyed you, would you have survived? — — Is divine omniscience compatible with human freedom? — — Is memory stored or reconstructed? — — Is reality fundamentally digital? — — Is salvation, liberation, or fulfillment individual or communal? — — Is the late-stage dementia patient still the person their spouse married? — — Is truth universal, tradition-bound, situated, or constructed? — — What happens to "you" when you die? — — What kind of religious-theological authority does the tradition recognize? — — What makes someone the same person over time? — — Who is the moral primary — the individual, the community, the cosmos, the class, or the species? — —
Information · 4 dilemmas, all mainstream
Is anything truly lost when someone forgets? Information is lost when a mind forgets; matter and energy continue, but the pattern is gone. 51% Does deleting your data online destroy something real? Information is genuinely lost when the substrate that hosted it goes; deletion really destroys. 51% Could the dead, in principle, be brought back? The information dissipates with the substrate; restoration is in principle impossible. 51% Is forgiveness ontologically possible? The offense is locally constituted by its substrate; when the substrate dissolves, the offense genuinely passes away. 51%
← #1546 Theological Tractates (Opuscula Sacra) All Works #1548 Intelligent Machinery →