7 Essential Words of Fall
1937, named for English mathematician and computer pioneer Alan M. Turing (1912-1954), who described such a device in 1936.
|Turing machine |
An abstract model of a computing device, used in mathematical studies of computability. A Turing machine takes a tape with a string of symbols on it as an input, and can respond to a given symbol by changing its internal state, writing a new symbol on the tape, shifting the tape right or left to the next symbol, or halting. The inner state of the Turing machine is described by a finite state machine. It has been shown that if the answer to a computational problem can be computed in a finite amount of time, then there exists an abstract Turing machine that can compute it.