On Computable Numbers, with an Application to the Entscheidungsproblem

A. M. Turing

Published 1936 · Proceedings of the London Mathematical Society · Journal article

Summary

Turing introduced an abstract model of computation—later called the Turing machine—to make precise the notion of a function being effectively calculable, defining 'computable numbers' as those whose decimals can be produced by such a machine. He proved the existence of a universal machine able to simulate any other and showed that some well-defined problems, including the halting problem, are not computable. Using these results he demonstrated that Hilbert's Entscheidungsproblem (decision problem) for first-order logic has no general algorithmic solution.

Key findings

Defined computability via an abstract automaton (the Turing machine), giving a rigorous formalization of 'effective procedure' / algorithm.
Established the existence of a universal Turing machine capable of computing anything any specific Turing machine can compute.
Proved that certain problems are undecidable and used this to give a negative answer to the Entscheidungsproblem.

Subjects & keywords

Mathematics computability turing machines mathematical logic entscheidungsproblem theory of computation

Cite this paper

APA

A. M. Turing (1936). On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society. https://doi.org/10.1112/plms/s2-42.1.230

BibTeX

@article{turing1936computable,
  author    = {A. M. Turing},
  title     = {On Computable Numbers, with an Application to the Entscheidungsproblem},
  journal   = {Proceedings of the London Mathematical Society},
  year      = {1936},
  doi       = {10.1112/plms/s2-42.1.230},
  url       = {https://doi.org/10.1112/plms/s2-42.1.230}
}