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, etc. We will proceed to do this, and also to show that the computable numbers include all numbers which could naturally be regarded as computable. According to my definition, a number is computable if its decimal can be written down by a machine.
✨ Summary
In his seminal 1936 paper, Alan M. Turing introduced the concept of ‘computable numbers,’ which can be calculated by a theoretical construct now known as the Turing Machine. This abstract computational device laid the groundwork for modern theories of computation and computability. Central to Turing’s argument was the negative resolution of the Entscheidungsproblem, a challenge in formal logic to identify an algorithm that could correctly resolve all mathematical statements. Turing demonstrated that such an algorithm could not exist because there are problems that are inherently uncomputable.
The impact of Turing’s work is profound and widespread. It has influenced fields as diverse as computability theory, algorithms, programming language design, and even the philosophy of mind by shaping ideas on artificial intelligence and the concept of mechanical calculation. The concept of a ‘Turing Machine’ remains fundamental to computer science as a model of general computing processes.
Turing’s paper has been cited extensively and inspired a wide array of research, including but not limited to Turing’s work on the artificial intelligence test known as the Turing Test, and ongoing research into quantum computing. Some influential citations include: - Davis, M. (1958). ‘Computability and Unsolvability’. McGraw-Hill Book Company. source - Hodges, A. (1983). ‘Alan Turing: The Enigma’. Princeton University Press. source - Sipser, M. (2006). ‘Introduction to the Theory of Computation’. Cengage Learning. source
The paper continues to be a cornerstone in both theoretical and applied disciplines, underscoring the limitations and capabilities of computation in the context of both classical systems and emerging computational models.