On Computable Numbers, with an Application to the Entscheidungsproblem
đź“ś Abstract
The "computable" numbers may be described briefly as the real numbers whose expressions as a decimal are calculable by finite means. Although the subject of this paper is ostensibly the computable numbers, it is almost equally easy to define and investigate computable functions of an integral variable or a real or computable variable. We can also define and investigate computable predicates, and so forth. The fundamental problem involved is the description of the range of the computable numbers. The real question at issue is "What are the possible processes which can be carried out in computing a number?" The present paper is concerned with the extent and limitations of mechanistic computing procedures. The main results of the paper are concerned with establishing the equivalence between "computability" by means of a human computer working in accordance with an algorithm and the "computability" by means of a machine constructed according to the logical principles set out in the paper. The paper also introduces a number of new concepts such as "Turing machines", the demonstration of the unsolvability of the "halting problem", the establishment of the first result of the "computability" of every effective process, and the fact that not every effective process is computable.
✨ Summary
Alan Turing’s seminal paper, “On Computable Numbers, with an Application to the Entscheidungsproblem,” published in November 1936, introduced the concept of what is now called a “Turing machine.” This theoretical construct provided a formal foundation for defining algorithms and computability, forming the basis for modern computer science. Turing’s paper resolved a fundamental problem in mathematical logic known as the Entscheidungsproblem posed by David Hilbert, demonstrating that there are limits to what can be computed by proving the existence of undecidable problems. The paper further established the equivalence between a human following a computational algorithm and a machine performing the computation.
Turing’s work has had a profound and lasting impact on the field of computer science, particularly influencing theories of computation and complexity, and laying the groundwork for the development of the modern computer. Its influence extends far beyond academia into practical applications in the industry, such as algorithm design, computer engineering, artificial intelligence, and cryptography.
The paper is widely cited and referenced in various research articles and books on computability theory and the history of computing. Some notable references include: 1. Davies, M., “Turing’s Vision: The Birth of Computer Science,” OUP, 2012. 2. Copeland, B. J., “The Essential Turing,” Oxford University Press, 2004. 3. Hodges, A., “Alan Turing: The Enigma,” Vintage, 2014. 4. Sipser, M., “Introduction to the Theory of Computation,” Cengage Learning, 2012. 5. Rogers, H., “Theory of Recursive Functions and Effective Computability,” MIT Press, 1987. 6. Boolos, G., and Jeffrey, R., “Computability and Logic,” Cambridge University Press, 2007.
These references indicate the paper’s significance in shaping the discourse in computability and theoretical computer science.