What is computation? The Turing machine

Turing made his proof of the decision problem or entscheidungsproblem in 1936, before there were any programmable computers. He was concerned with what can be computed or calculated by a human who is following definite rules, i.e. by a human doing mathematics as the formalists say it should be done.

He first had to formalise the notion of a ``definite method''. He did this by constructing a mathematical model of somebody following a definite set of rules. This model was the Turing machine. It:

• used a finite alphabet of symbols. Clearly, this is what mathematicians use when working.

• wrote these on tape divided into squares, each square capable of holding one symbol. This is an idealisation of the 2-d piece of paper that the mathematician works on. Its two-dimensionality adds nothing essential, so without loss of generality, we can model it as a 1-d tape.

• had a finite number of possible ``states of mind''. If the number of states of mind were infinite, then some states would have to be arbitrarily close, and hence could not be distinguished. (This also applies to the alphabet of symbols.)

• can at any time inspect one symbol, that which is in the tape square under its ``eye''. (The ``eye'' is usually termed a read head.)

• has a behaviour which is determined solely by the current symbol under its ``eye'', plus its current ``state of mind''. In effect, the machine contains a ``state table'' which maps every combination of these two to a new state plus some behaviour. This is the assumption of physical determinism. You can think of many machines which embody such state tables: e.g. a coffee machine, whose current ``state of mind'' is determined by the value of the coins inside it, or a washing machine, whose current ``state of mind'' is determined by the signals from its timer.

• builds its behaviour from very simple operations. It can write a symbol, change its state of mind, move the tape left or right. We lose no generality by restricting ourselves to such simple operations, because we can combine them to produce arbitrarily complex behaviours.

See the essay by Andrew Hodges in The Universal Turing Machine edited by Herken (PSY KD:H 42) for a summary of the history behind Turing's work. Other essays describe the mathematical background, but may be too technical. Penrose pages 47-48 explains why the Turing machine is an adequate model of what human mathematicians do when following rules.

• The Universal Turing Machine