On Computable Numbers

On Computable Numbers. "On Computable Numbers, with an Application to the Entscheidungsproblem" is a seminal 1936 paper by the British mathematician and logician Alan Turing. It introduced the abstract computing model now known as the Turing machine, providing a formal definition of algorithm and computation. The paper's central achievement was a proof that the Entscheidungsproblem, a key challenge posed by David Hilbert, is unsolvable, establishing fundamental limits to mathematical logic and computation.

Historical context and publication

The paper emerged from the intense foundational debates in early 20th-century mathematics and logic. In the 1920s, David Hilbert of the University of Göttingen had proposed the Entscheidungsproblem, seeking a mechanical procedure to determine the truth of any statement in formal systems like first-order logic. This was part of Hilbert's program to secure the foundations of mathematics. Concurrently, work by Alonzo Church on lambda calculus and Kurt Gödel with his incompleteness theorems had shaken the field. Turing developed his ideas independently while at King's College, Cambridge, under the influence of Max Newman. The paper was published in the Proceedings of the London Mathematical Society in 1936, shortly after Church published his own negative solution using different methods. Turing later added an appendix demonstrating the equivalence of his approach with Church's thesis.

Main concepts and definitions

Turing's paper formally defined a "computable number" as one whose decimal expansion could be produced by a mechanical process. To rigorously capture "mechanical process," he invented the conceptual device now called a Turing machine. This abstract machine consists of a limitless tape, a read-write head, a finite set of states, and a table of instructions. He described the machine's operation through a series of simple, atomic actions: reading a symbol, writing a symbol, moving the head, and changing state. Turing argued that any function calculable by a human following a fixed procedure could be computed by such a machine, an assertion later known as the Church–Turing thesis. This provided the first mathematically precise characterization of an effective method or algorithm.

The halting problem and undecidability

A pivotal construction in the paper is the proof that no general algorithm exists to decide whether an arbitrary Turing machine will halt. Turing demonstrated this by defining a universal machine capable of simulating any other Turing machine's description. Using a diagonalization argument reminiscent of Georg Cantor and Kurt Gödel, he showed that assuming a machine could solve the halting problem leads to a logical contradiction. This result directly implied the unsolvability of the Entscheidungsproblem for first-order logic, as a procedure for it could be used to solve the halting problem. This established the existence of undecidable problems within formal systems, a profound limitation on mathematical logic and automated deduction.

Impact and legacy

The impact of "On Computable Numbers" is immense and interdisciplinary. It laid the theoretical groundwork for the entire field of computer science, influencing pioneers like John von Neumann in the design of the von Neumann architecture. The concepts of the Turing machine and universal Turing machine became the bedrock of computability theory and computational complexity theory. During World War II, Turing applied these logical insights to cryptanalysis at Bletchley Park, contributing to breaking the Enigma machine. The paper also deeply influenced philosophy of mind, with Turing's later work on the Turing test for artificial intelligence stemming from these foundations. It is considered a cornerstone of theoretical computer science and mathematical logic.

Relationship to Turing machines

The paper is the original source for the definition and analysis of Turing machines. Turing introduced them not as a blueprint for physical computers but as a thought experiment to explore the limits of mechanical calculation. The universal Turing machine described in the paper is the theoretical forerunner of the stored-program computer. The paper's rigorous treatment showed that Turing machines could compute all effectively calculable functions, establishing them as a standard model of computation. This model later allowed Alonzo Church and Stephen Kleene to formalize recursive function theory and enabled precise study in fields like algorithmic information theory pioneered by Andrey Kolmogorov and Gregory Chaitin.

Category:1936 documents Category:Mathematics papers Category:Theoretical computer science