Turing Machine

The Turing machine is an abstract mathematical model of computation: a device that reads and writes symbols on an endless tape one cell at a time, moving left or right and changing its own internal state according to a fixed table of rules. Alan Turing introduced it in his 1936 paper On Computable Numbers, with an Application to the Entscheidungsproblem, using the machine to prove that no general method can decide in advance, for every possible program and input, whether that program will eventually halt or run forever, the halting problem, and thereby that not every mathematical question can be settled by a fixed mechanical procedure. The same paper showed that a single universal machine of this kind, given the description of any other Turing machine on its own tape, can carry out whatever that other machine would have done, the theoretical basis for a general purpose computer able to run whatever program it is given rather than being built for one task alone.