On Computable Numbers with an Application to the Entscheidungsproblem

E13826

computer science foundational work mathematics paper scientific paper

"On Computable Numbers, with an Application to the Entscheidungsproblem" is Alan Turing’s landmark 1936 paper that introduced the Turing machine model and founded the formal study of computability and the limits of algorithmic decision procedures.

Try in SPARQL Jump to: Surface forms Disambiguation Statements Elicitation Referenced by

AI illustration

All labels observed (6)

Label	Occurrences
On Computable Numbers, with an Application to the Entscheidungsproblem	3
Entscheidungsproblem	1
On Computable Numbers	1
On Computable Numbers with an Application to the Entscheidungsproblem canonical	1
Turing 1936 paper	1
Turing’s paper on computable numbers and the Entscheidungsproblem	1

How this entity was disambiguated

This entity first appeared as the object of triple T123963 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.

NED1 Entity disambiguation (via context triple) gpt-5-mini-2025-08-07

Target entity: On Computable Numbers with an Application to the Entscheidungsproblem
Context triple: [Turing machine, describedInWork, On Computable Numbers with an Application to the Entscheidungsproblem]

A. Turing machine
A Turing machine is an abstract computational model that manipulates symbols on an infinite tape according to a set of rules, providing a formal foundation for the concept of algorithm and computability.
B. A Symbolic Analysis of Relay and Switching Circuits
A Symbolic Analysis of Relay and Switching Circuits is Claude Shannon’s landmark 1937 master’s thesis that founded modern digital circuit design by applying Boolean algebra to relay and switching systems.
C. Principia Mathematica
Principia Mathematica is a landmark three-volume work in mathematical logic and the foundations of mathematics, co-authored by Bertrand Russell and Alfred North Whitehead, which aimed to derive all mathematical truths from a formal system of symbolic logic.
D. A Mathematical Theory of Communication
A Mathematical Theory of Communication is Claude Shannon’s landmark 1948 paper that founded information theory by rigorously defining concepts like information, entropy, and channel capacity.
E. Man-Computer Symbiosis
Man-Computer Symbiosis is a seminal 1960 essay by J. C. R. Licklider that envisioned interactive, cooperative partnerships between humans and computers, laying conceptual foundations for modern interactive computing and the internet.
F. None of above. chosen
G. Unsure - the case is ambiguous/there is not enough information to decide.

NED2 Entity disambiguation (via description) gpt-5-mini-2025-08-07

Target entity: On Computable Numbers with an Application to the Entscheidungsproblem
Target entity description: "On Computable Numbers, with an Application to the Entscheidungsproblem" is Alan Turing’s landmark 1936 paper that introduced the Turing machine model and founded the formal study of computability and the limits of algorithmic decision procedures.

A. Turing machine
A Turing machine is an abstract computational model that manipulates symbols on an infinite tape according to a set of rules, providing a formal foundation for the concept of algorithm and computability.
B. A Symbolic Analysis of Relay and Switching Circuits
A Symbolic Analysis of Relay and Switching Circuits is Claude Shannon’s landmark 1937 master’s thesis that founded modern digital circuit design by applying Boolean algebra to relay and switching systems.
C. Principia Mathematica
Principia Mathematica is a landmark three-volume work in mathematical logic and the foundations of mathematics, co-authored by Bertrand Russell and Alfred North Whitehead, which aimed to derive all mathematical truths from a formal system of symbolic logic.
D. A Mathematical Theory of Communication
A Mathematical Theory of Communication is Claude Shannon’s landmark 1948 paper that founded information theory by rigorously defining concepts like information, entropy, and channel capacity.
E. Man-Computer Symbiosis
Man-Computer Symbiosis is a seminal 1960 essay by J. C. R. Licklider that envisioned interactive, cooperative partnerships between humans and computers, laying conceptual foundations for modern interactive computing and the internet.
F. None of above. chosen

Statements (46)

Predicate	Object
instanceOf	computer science foundational work ⓘ mathematics paper ⓘ scientific paper ⓘ
academicDiscipline	foundations of mathematics ⓘ logic in computer science ⓘ
addressesProblem	Entscheidungsproblem ⓘ
author	Alan Turing ⓘ
citedAs	Turing 1936 paper ⓘ linked to: On Computable Numbers with an Application to the Entscheidungsproblem
countryOfPublication	United Kingdom ⓘ
field	computability theory ⓘ mathematical logic ⓘ theoretical computer science ⓘ
followedBy	Computability and λ-definability ⓘ linked to: lambda calculus
hasPart	application to the Entscheidungsproblem ⓘ construction of a universal machine ⓘ definition of automatic machines ⓘ proof of the existence of uncomputable numbers ⓘ
historicalSignificance	foundational paper in computability theory ⓘ one of the founding works of theoretical computer science ⓘ
influenced	development of computer science ⓘ recursion theory ⓘ theory of algorithms ⓘ
influencedBy	David Hilbert’s Entscheidungsproblem ⓘ linked to: Entscheidungsproblem Kurt Gödel’s work on formal systems ⓘ
introducesConcept	Turing machine ⓘ computable function ⓘ computable real number ⓘ universal Turing machine ⓘ linked to: Turing machine
language	English ⓘ
mainSubject	Entscheidungsproblem ⓘ linked to: On Computable Numbers with an Application to the Entscheidungsproblem Turing machines ⓘ linked to: Turing machine computable numbers ⓘ
provesResult	existence of uncomputable numbers ⓘ existence of undecidable problems ⓘ unsolvability of the Entscheidungsproblem ⓘ
publishedIn	Proceedings of the London Mathematical Society ⓘ
publisher	London Mathematical Society ⓘ
relatedTo	Church–Turing thesis ⓘ Gödel’s incompleteness theorems ⓘ linked to: Gödel's incompleteness theorems lambda calculus ⓘ
shortTitle	On Computable Numbers ⓘ linked to: On Computable Numbers with an Application to the Entscheidungsproblem
timePeriod	20th century ⓘ
title	On Computable Numbers, with an Application to the Entscheidungsproblem ⓘ linked to: On Computable Numbers with an Application to the Entscheidungsproblem
usesMethod	diagonalization ⓘ encoding of machines as numbers ⓘ
yearPublished	1936 ⓘ

How these facts were elicited

Referenced by (8)

Full triples — surface form annotated when it differs from this entity's canonical label.

Turing machine → describedInWork → On Computable Numbers with an Application to the Entscheidungsproblem ⓘ

Alan Turing → notableWork → On Computable Numbers, with an Application to the Entscheidungsproblem ⓘ