University of Alberta Dictionary of Cognitive Science: Turing Machine

A Turing machine is an abstract notion of computing that was invented by mathematician Alan Turing to be used in his examination of David Hilbert’s decidability problem (Turing, 1983). A Turing machine is a simple but enormously powerful device for manipulating symbols according to a set of rules. The machine consists of two parts. The first is an infinitely long ticker-tape memory, with the tape divided into cells, with each cell capable of storing one (and only one) symbol. The second is a machine head, which is responsible for manipulating the symbols stored on the tape. The machine head can read symbols from the tape, and can write symbols to the tape. It can move left or right along the tape, one cell at a time, permitting the tape to be used as a memory. The machine head is always in a particular physical state at any given time. The behavior of the machine at any moment is dictated by a machine table (Where will it move? What will it write? What state will it adopt?). The table stores the possible actions of the machine head. The current symbol being read, and the current machine state, are all that is required to select one action to be performed from the machine table.

In essence, a Turing machine can be viewed as a question answering device. A question is written on the tape, and a Turing machine manipulates the tape’s symbols. When the Turing machine stops, it will have written the answer to the question on the tape. The kind of question that is answered is defined by the machine table: for instance, one example machine table would enable a Turing machine to add any two integers together. A special machine table creates a particular device called the universal Turing machine. This machine can pretend to be any possible Turing machine, provided that the machine table of the to-be-mimicked machine is encoded on the universal Turing machine’s tape. “It followed that one particular machine could simulate the work done by any machine…It would be a machine to do everything, which was enough to give anyone pause for thought” (Hodges, 1983, p. 104). The universal Turing machine is the inspiration for the modern digital computer, and is the foundation of classical cognitive science.

References:

Hodges, A. (1983). Alan Turing: The Enigma Of Intelligence. London: Unwin Paperbacks.
Turing, A. M. (1936). On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, Series 2h, 42, 230-265.

(Added January 2010)