Turing machine

(Page originally by Lars H, but feel free to add material.)

The Turing machine, named after Alan Turing [L1 ], 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).

Each Turing machine can be thought of as an implementation of an algorithm. The input consists of the symbols initially written on the tape. The output consists of the symbols that are on the tape when the machine halts. The algorithm itself is completely described by the transition function of the finite state automaton and the function that decides which operation the machine should perform.

A universal Turing machine is one which can simulate any other Turing machine. In other words, given the same input tape, it will produce the same output. A universal Turing machine can be made by creating a machine which takes as input first a description of the machine to simulate, and then the actual input. The description of the machine to simulate is an encoding of its finite state automaton as a string of symbols.

There are a couple of obvious variations of the above description whose equivalence should be pointed out.

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.