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¶
10 citations across 10 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 bibliography-only (no longer cited at marker 015); supports the T3/T5 Church–Turing undecidability of first-order validity, not the completeness claim.
- 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.
Verification¶
This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.
Registry ID ref:1b5cfd2a80e3 · see in the full table