On Computable Numbers, with an Application to the Entscheidungsproblem.¶
Turing, A. M. (1936). On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 42(1), 1936-37.
Cited by¶
11 citations across 11 artifacts.
Each citation links to the sentence it supports in the citing article.
Primes¶
- Algorithm
- The abstract-machine-execution model independence (Turing, 1936)
This sourceDefines computability via the abstract Turing machine, establishing machine-model independence as the criterion for an effective procedure.
- The abstract-machine-execution model independence (Turing, 1936)
- Computability
- A problem is computable, in the classical sense captured equivalently by Turing machines, the λ-calculus, μ-recursive functions, and a dozen other formalisms unified by the Church–Turing thesis
This sourceDefines the Turing machine, proves the halting problem undecidable by diagonalization, and (with Church) grounds the Church–Turing thesis that the computable functions are model-invariant.
- A problem is computable, in the classical sense captured equivalently by Turing machines, the λ-calculus, μ-recursive functions, and a dozen other formalisms unified by the Church–Turing thesis
- Decidability Computability
- Computability theory and computer science. The halting problem, the Entscheidungsproblem, and the decidability of first-order theories: the procedure is a Turing machine, the instance an input string, and termination is halting with a verdict.
This sourceProves the halting problem undecidable and gives the negative answer to the Entscheidungsproblem via the Turing-machine model.
- Computability theory and computer science. The halting problem, the Entscheidungsproblem, and the decidability of first-order theories: the procedure is a Turing machine, the instance an input string, and termination is halting with a verdict.
- Deductive Reasoning
This sourceDefines computability via the Turing machine and proves the undecidability of the Entscheidungsproblem. WebSearch confirmed venue, pages, and content. Now.
- Diagonal Impossibility
- The diagonal construction builds a new program D that takes a program p, consults H on p applied to itself — runs H(p, p) — and then does the opposite: if H says p(p) halts, D loops forever; if H says p(p) loops, D halts.
This sourceThe halting problem proved undecidable by a diagonal self-application construction.
- The diagonal construction builds a new program D that takes a program p, consults H on p applied to itself — runs H(p, p) — and then does the opposite: if H says p(p) halts, D loops forever; if H says p(p) loops, D halts.
- Discreteness
- … model-checking, exhaustive verification), graph-theoretic analysis (paths, flows, matchings, colorings, isomorphisms), integer programming (optimization with integer constraints, branch-and-bound, cutting-plane methods), formal-language and automata theory (parsing, regular-expression matching, model-checking
This sourceFoundational definition of computability via the abstract Turing machine, establishing machine-model independence as the criterion for what counts as an effective procedure.
- … model-checking, exhaustive verification), graph-theoretic analysis (paths, flows, matchings, colorings, isomorphisms), integer programming (optimization with integer constraints, branch-and-bound, cutting-plane methods), formal-language and automata theory (parsing, regular-expression matching, model-checking
- Function (Mapping)
- Many algorithms can compute the same function; some functions have no algorithm at all (uncomputable functions, as established by Turing's work
This sourceFoundational definition of computability via the abstract Turing machine, establishing machine-model independence as the criterion for what counts as an effective procedure.
- Many algorithms can compute the same function; some functions have no algorithm at all (uncomputable functions, as established by Turing's work
- Infinity
- In theoretical computer science, infinity underwrites computability theory (uncountably many functions ℕ → ℕ exist but only countably many algorithms, so undecidable problems must exist — a cardinality argument extending Cantor (1874) and developed for computability by Turing (1936)
This sourceFoundational definition of computability via the abstract Turing machine, establishing machine-model independence as the criterion for what counts as an effective procedure.
- In theoretical computer science, infinity underwrites computability theory (uncountably many functions ℕ → ℕ exist but only countably many algorithms, so undecidable problems must exist — a cardinality argument extending Cantor (1874) and developed for computability by Turing (1936)
- Meta-Symbolic Reflection
- Turing 1936
This sourceFoundational definition of computability via the abstract Turing machine, establishing machine-model independence as the criterion for what counts as an effective procedure.
- Turing 1936
- Universality
- Computer science: Turing machines, lambda calculus, cellular automata, and register machines compute exactly the same class of functions despite radically different architectures — the Church–Turing thesis is a universality claim about computational substrates.
This sourceDefines the universal machine and the computable functions, the basis of the Church–Turing universality claim that disparate computational models compute the same class.
- Computer science: Turing machines, lambda calculus, cellular automata, and register machines compute exactly the same class of functions despite radically different architectures — the Church–Turing thesis is a universality claim about computational substrates.
Mechanisms¶
- Decidability Triage Worksheet
- The touchstone the worksheet exists to catch is the halting problem — the standing reminder that some yes/no questions admit no total procedure at all
This sourceProves that some formally posed decision questions admit no general finite procedure.
- The touchstone the worksheet exists to catch is the halting problem — the standing reminder that some yes/no questions admit no total procedure at all
Verification¶
Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.
Does it back the claim? Not recorded. Neither this nor any other of the 11 citations of this work carries a recorded support check.
Was it audited? Yes. A second, independent pass read the citation against the article text and recorded a verdict.
Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.
See how references were verified.
Registry ID ref:1b5cfd2a80e3 · see in the full table