On Computable Numbers with an Application to the Entscheidungsproblem
E13826
"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.
Aliases (4)
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
→
|
| countryOfPublication |
United Kingdom
→
|
| field |
computability theory
→
mathematical logic → theoretical computer science → |
| followedBy |
Computability and λ-definability
→
|
| 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
→
Kurt Gödel’s work on formal systems → |
| introducesConcept |
Turing machine
→
computable function → computable real number → universal Turing machine → |
| language |
English
→
|
| mainSubject |
Entscheidungsproblem
→
Turing machines → 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 → lambda calculus → |
| shortTitle |
On Computable Numbers
→
|
| timePeriod |
20th century
→
|
| title |
On Computable Numbers, with an Application to the Entscheidungsproblem
→
|
| usesMethod |
diagonalization
→
encoding of machines as numbers → |
| yearPublished |
1936
→
|
Referenced by (6)
| Subject (surface form when different) | Predicate |
|---|---|
|
On Computable Numbers, with an Application to the Entscheidungsproblem
("Turing 1936 paper")
→
|
citedAs |
|
Turing machine
→
|
describedInWork |
|
On Computable Numbers, with an Application to the Entscheidungsproblem
("Entscheidungsproblem")
→
|
mainSubject |
|
Alan Turing
("On Computable Numbers, with an Application to the Entscheidungsproblem")
→
|
notableWork |
|
On Computable Numbers, with an Application to the Entscheidungsproblem
("On Computable Numbers")
→
|
shortTitle |
|
On Computable Numbers, with an Application to the Entscheidungsproblem
("On Computable Numbers, with an Application to the Entscheidungsproblem")
→
|
title |