On Computable Numbers, with an Application to the Entscheidungsproblem
We may compare a man in the process of computing a real number to a machine which is only capable of a finite number of conditions.
¶
The a-machine
¶
Turing describes an automatic machine: finite states, an infinite tape, read/write head. Simple enough to reason about, powerful enough to simulate any effective procedure. The Turing machine is the standard model of computation.
¶
The halting problem
¶
Some questions have no general algorithmic answer. Turing proved the Entscheidungsproblem undecidable: no machine can decide every true statement in formal logic. Computation has outer walls.
¶
Before computers existed
¶
Turing wrote this in 1936, a decade before electronic stored-program computers. The paper is pure mathematics that turned out to be the spec sheet for an industry.