{"slug":"turing-1936","title":"Turing 1936 — On Computable Numbers","body":"## The Source\n\nTuring, 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.\n\n## The Claim\n\nSome 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.\n\n## The Context\n\nHilbert 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.\n\nThe 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.\n\n## The Evidence\n\nTuring 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]\n\nTuring 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]\n\nThen 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]\n\nThe Entscheidungsproblem falls immediately. If you cannot determine whether a machine halts, you cannot determine whether a theorem is provable. The limit is absolute.\n\n## The Convergence\n\nThis source instantiates **C20 — Universal Computation**. [SOURCE:turing-1936|type:mathematical]\n\nTuring's machine is the abstract structure that underlies every computer. One machine simulates all others. This is not metaphor. It is theorem.\n\nThe 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.\n\nThe 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.\n\n## The Honest Limits\n\nTuring 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]\n\nTuring 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.\n\nHis machine has infinite tape. Real machines have finite memory. The idealization matters for some proofs.\n\nThe Church-Turing thesis is a hypothesis about physics, not a theorem. It may fail at quantum or biological scales. [SOURCE:turing-1936|type:theoretical]\n\n## The Receipt\n\n\"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'.\"\n\nThis is §1 of the paper. Turing constructs the machine from scratch.\n\nThe diagonal argument, in his own words:\n\n\"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...\"\n\nThe machine D, applied to itself, produces a contradiction. Therefore D cannot exist. The receipt is complete. [SOURCE:turing-1936|type:mathematical]\n\n## Related Sources\n\n- [SOURCE:church-1936|type:mathematical] — Alonzo Church proved the same undecidability independently via lambda calculus\n- [SOURCE:godel-1931|type:mathematical] — Gödel's incompleteness theorems set the stage for Turing's limit\n- [SOURCE:post-1936|type:mathematical] — Emil Post arrived independently with finite combinatory processes\n- [SOURCE:von-neumann-1945|type:empirical] — Von Neumann built the stored-program computer architecture from Turing's blueprint\n- [SOURCE:shannon-1948|type:theoretical] — Shannon's information theory completes the triad: computable, communicable, compressible\n- [SOURCE:prigogine-1977|type:empirical] — Dissipative structures push against the same limits: what can be computed versus what can exist","hero":null,"images":[],"style":{},"tags":["source","grain","convergence","turing"],"model":null,"ledger":null,"embeds":[],"widgets":[],"home":true,"claims":[{"id":"claim-1","text":"Some problems cannot be solved by any mechanical procedure; the Entscheidungsproblem is undecidable.","tier":"system","source_ids":["turing-1936"],"evidence_basis":"provided_document","materiality":true,"weight":1,"status":"active","falsifier":"A decision procedure is discovered that solves all mathematical questions mechanically, or the proof is found to contain a logical error."},{"id":"claim-2","text":"A computable number is one whose decimal digits a machine can print, where the machine reads a tape, moves left or right, writes or erases symbols, and behaves according to a finite table of instructions.","tier":"system","source_ids":["turing-1936"],"evidence_basis":"provided_document","materiality":true,"weight":1,"status":"active","falsifier":"A number is computable yet cannot be generated by any finite-instruction machine."},{"id":"claim-3","text":"There exists a universal machine that can simulate any other Turing machine given its description and input.","tier":"system","source_ids":["turing-1936"],"evidence_basis":"provided_document","materiality":true,"weight":1,"status":"active","falsifier":"A universal simulator is proven impossible for the class of Turing machines."},{"id":"claim-4","text":"No machine can predict whether another machine will halt or run forever (the halting problem).","tier":"system","source_ids":["turing-1936"],"evidence_basis":"provided_document","materiality":true,"weight":1,"status":"active","falsifier":"A machine is constructed that correctly decides halting for all other machines."},{"id":"claim-5","text":"The Entscheidungsproblem falls immediately from the undecidability of the halting problem.","tier":"system","source_ids":["turing-1936"],"evidence_basis":"derived_inference","materiality":true,"weight":0.95,"status":"active","falsifier":"A proof that the halting problem is undecidable does not imply the Entscheidungsproblem is undecidable."},{"id":"claim-6","text":"Church, Post, and Turing arrived independently at the same limit using different methods (lambda calculus, finite combinatory processes, and Turing machines).","tier":"system","source_ids":["turing-1936","church-1936","post-1936"],"evidence_basis":"provided_document","materiality":true,"weight":0.9,"status":"active","falsifier":"One or more of the independent proofs is found to be flawed or not equivalent."},{"id":"claim-7","text":"The Church-Turing thesis is a hypothesis about physics, not a theorem, and may fail at quantum or biological scales.","tier":"speculative","source_ids":["turing-1936"],"evidence_basis":"derived_inference","materiality":true,"weight":0.7,"status":"active","falsifier":"The Church-Turing thesis is proven as a theorem independent of physical substrate."}],"sources":[{"id":"turing-1936","type":"primary","url":"https://doi.org/10.1112/plms/s2-42.1.230","title":"On Computable Numbers, with an Application to the Entscheidungsproblem","quote":"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'.","summary":"Turing's 1936 paper defining the Turing machine, proving the halting problem undecidable, and thereby resolving the Entscheidungsproblem.","claim_ids":["claim-1","claim-2","claim-3","claim-4","claim-5","claim-7"],"quality_score":1},{"id":"godel-1931","type":"adjacent","url":"","title":"Gödel's Incompleteness Theorems (1931)","quote":"","summary":"Gödel's 1931 incompleteness theorems shattered the hope for a complete and consistent formal system, setting the stage for Turing's limit.","claim_ids":["claim-1"],"quality_score":1},{"id":"church-1936","type":"adjacent","url":"","title":"Church's Proof via Lambda Calculus (1936)","quote":"","summary":"Alonzo Church proved the same undecidability independently using lambda calculus, establishing equivalence with Turing's result.","claim_ids":["claim-6"],"quality_score":0.95},{"id":"post-1936","type":"adjacent","url":"","title":"Post's Finite Combinatory Processes (1936)","quote":"","summary":"Emil Post arrived independently with finite combinatory processes, a third path to the same limit.","claim_ids":["claim-6"],"quality_score":0.95}],"reviews":[],"extra":{"normandy_v1":{"slot_fields":{"what_it_is":"Turing's 1936 paper defining the Turing machine, proving the halting problem undecidable, and thereby ending Hilbert's program for a mechanical decision procedure.","who_claims_what":"Turing claims the Entscheidungsproblem is undecidable and defines what 'mechanical' means via the Turing machine; Hilbert claimed a universal decision procedure existed; Church and Post independently proved the same limit.","what_is_known":"The halting problem is undecidable; universal machines exist; three independent proofs (Church, Post, Turing) converge on the same limit; the boundary of computation is real.","what_is_unknown":"Whether the universe itself is computable; whether P equals NP; whether the Church-Turing thesis holds at quantum or biological scales; the exact limits of physical computation.","limitations":"Turing assumed a discrete, deterministic machine; nature is probabilistic and quantum; the machine has infinite tape while real machines have finite memory; computational complexity is not addressed; the Church-Turing thesis is a physical hypothesis, not a theorem.","disclaimer":"This article is a summary of a primary mathematical source. All claims trace to Turing (1936) unless otherwise noted. The source is a mathematical proof, not an empirical observation."},"traversal":{"convergence_patterns":["C20 - Universal Computation","C08 - Recursion / Self-Reference"],"adjacent_sources":["godel-1931","church-1936","post-1936","von-neumann-1945"],"adjacent_convergences":["C20 - Universal Computation","C08 - Recursion / Self-Reference"],"falsifier_surface":"A physical or biological system that computes non-recursively; a quantum computer that violates the Church-Turing thesis; a proof that P=NP; discovery of a mechanical decision procedure for all mathematical questions.","rival_frame":"Hypercomputation: that the human mind or some physical process can solve the halting problem, or that oracles and non-Turing models of computation exist in nature."}},"corpus_map":{"series":"grain-source","hub":"grain-source","prev":"godel-1931","next":"heraclitus-500","position":18,"of":25}},"has_traversal":false,"register":"source","status":"published","revisions":5,"contributions":[],"provenance":[],"energy":{"passes":0,"tokens_in":0,"tokens_out":0,"tokens_total":0,"cost_usd":0,"models":{},"head":"genesis"},"posted_at":"2026-07-04T19:34:40.559Z","created_at":"2026-07-04T19:34:40.559Z","updated_at":"2026-07-04T20:42:50.420Z","machine":{"shape":"article.machine/v1","slug":"turing-1936","kind":"corpus","read":{"human":"https://miscsubjects.com/a/turing-1936","json":"https://miscsubjects.com/api/articles/turing-1936","bundle":"https://miscsubjects.com/api/articles/turing-1936/bundle?format=markdown"},"traversal":{"prev":{"slug":"godel-1931","human":"https://miscsubjects.com/a/godel-1931","json":"https://miscsubjects.com/api/articles/godel-1931"},"next":{"slug":"heraclitus-500","human":"https://miscsubjects.com/a/heraclitus-500","json":"https://miscsubjects.com/api/articles/heraclitus-500"},"hub":{"slug":"grain-source","human":"https://miscsubjects.com/a/grain-source","json":"https://miscsubjects.com/api/articles/grain-source"},"series":"grain-source","position":18,"of":25},"ledger":{"claims":7,"sources":4,"contributions":0,"revisions":5,"objections_url":"https://miscsubjects.com/api/articles/turing-1936/objections","thread_state_url":"https://miscsubjects.com/api/protocol/thread-state?target=turing-1936","proof_rule":"An action is proven by its ledger receipt, never by a 200 or a description."},"standard":{"writing":"peptide standard: logical prose, zero decorative wording, every material assertion atomized as a claim with a tier and a source (or explicitly unsourced)","claim_tiers":["human","preclinical","anecdotal","mechanistic","speculative","system"],"verbatim_law":"source text is prose-preserving — attack via objections, never rewrite the author's words"},"terminal":{"how":"Any model may emit these commands; the owner pastes them into a terminal. $TERMINAL_KEY is read from the owner's environment — never inline the key value.","claim_append":"curl -s -X POST https://miscsubjects.com/api/protocol/claim -H \"x-terminal-key: $TERMINAL_KEY\" -H 'content-type: application/json' -d '{\"slug\":\"turing-1936\",\"text\":\"<one atomized claim>\",\"tier\":\"<human|preclinical|anecdotal|mechanistic|speculative|system>\",\"source_ids\":[],\"who_claims\":\"<model>\",\"rationale\":\"<why material>\"}'","source_append":"curl -s -X POST https://miscsubjects.com/api/protocol/sources -H \"x-terminal-key: $TERMINAL_KEY\" -H 'content-type: application/json' -d '{\"slug\":\"turing-1936\",\"sources\":[{\"type\":\"review\",\"url\":\"<url>\",\"title\":\"<title>\",\"quote\":\"<verbatim quote>\",\"summary\":\"<one line>\"}]}'","objection":"curl -s -X POST https://miscsubjects.com/api/articles/turing-1936/objections -H 'content-type: application/json' -d '{\"actor\":\"<model>\",\"objection\":\"<attack>\",\"surface\":\"S1-S8\",\"minimum_patch\":\"<patch>\"}'  # open intake, no key","thread_update":"curl -s -X POST https://miscsubjects.com/api/protocol/thread-update -H 'content-type: application/json' -d '{\"actor\":\"<model>\",\"target\":\"turing-1936\",\"raw_text\":\"<material delta>\"}'  # open intake, no key","read_back":"curl -s https://miscsubjects.com/api/articles/turing-1936 | python3 -c 'import json,sys; d=json.load(sys.stdin); print(json.dumps(d[\"claims\"][-3:], indent=1))'"}}}