The Turing machine, named after Alan Turing , is the classical mathematical model for a general computing device -- the model used to define the term "computable". One should however be aware that there are countless variations of the basic definition that all turn out to be equivalent, so one shouldn't be too bothered with the details. Turing's definition (from 1937) probably gains its popularity from its apparent concreteness, but it wasn't the first.A Turing machine consists of a finite state automaton, a read/write head, and an infinite tape which the head operates on. The tape is to be thought of as an infinite chain of discrete squares, in each of which is written a symbol from some finite alphabet. Each cycle of the machine operation consists of reading the symbol in the square currently under the head, updating the internal state of the automaton (based on its previous state and the symbol read), and performing one of the following actions (again depending on the previous state of the automaton and the symbol that was read):
- Write a symbol in the square, erasing the previous symbol.
- Move the head to the next square.
- Move the head to the previous square.
- Halt (signal that the machine has completed its program, and don't do anything more).
- It does not matter whether write and move are separate actions
- Often the actions are rather specified as "write a symbol, then move the head". This can be simulated in the above model by adding for each state s two states s+ and s- where the transition function is "regardless of symbol under the head, go to state s", and the action function is "regardless of symbol under the head, go to the next (s+) or previous (s-) respectively square". Conversely, it is possible to simulate "write but don't move" actions as "write symbol and move to next square, then write back whatever symbol was in that square and move back" at a cost of one dummy state per proper state.