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 will confine ourselves, in the first instance, to computable numbers and to such computable functions of an integral variable. A number is computable if its decimal can be written down by a machine. In § 9 we shall show that certain large classes of numbers are computable. In § 11 it will be shown that the computable numbers are not enumerable. § 10 and 11 are devoted to theorems showing that certain classes of problems are undecidable. These results have some bearing on the problem of finding a general process for determining whether a given formula U is provable in a given logistic system; in particular, they show that if there is a general process for determining whether U is provable, then there is a corresponding process for determining sufficient mechanical facts about this system to show that U is provable.
✨ Summary
Alan Turing’s paper, “On Computable Numbers, with an Application to the Entscheidungsproblem,” published in 1936, is foundational in computer science and mathematics. The paper introduced the concept of a “Turing machine,” a theoretical construct that became crucial in the development of computer science. Turing’s work addressed the Entscheidungsproblem (decision problem), demonstrating that not all problems can be decided computationally. Turing machines laid the groundwork for modern theories of computation and complexity, significantly influencing the fields of automata theory and algorithmic processes. This paper also contributed to establishing the field of computability theory, introducing the notion of computable functions and numbers. Turing’s insights into undecidability and computation have had substantial historical influence, directly affecting the development of modern computers and influencing notable figures such as John von Neumann. The impact of this work is well-documented in various citations, such as those found in later research by Alonzo Church and digital computing innovations in the mid-20th century. Key references include citations in papers discussing theoretical computer science and logic, as seen in Church’s work on the concept of computability. Turing’s work has had enduring significance, as evidenced by its continued citation in computational theory research and its influence on the architecture of contemporary digital computers.