Universal Turing Machine

A universal Turing machine is a particular form of Turing machine that is capable of mimicking the behavior of any possible Turing machine (Hodges, 1983; Turing, 1936).  On the one hand, it has all the characteristics of any Turing machine: infinite ticker tape memory, machine head, and machine table.  On the other hand, from an external perspective – not the machine’s – the ticker tape is more elaborate than that for a standard Turing machine.  Instead of holding a to-be-answered question, it holds this question, a “scratch pad” area used as a temporary memory, and a description of the table of the to-be-mimicked machine.  That is, the ticker tape of the universal machine holds a program that tells the universal machine about the behavior of the machine that it will mimic.  The universal machine in essence moves back and forth between the program and the question (in a fashion controlled by the universal machine’s table) so that the machine treats the question as if its own machine table was the same as the one given on the tape.  The power of the universal Turing machine comes from its ability to follow the program that describes any possible Turing machine, meaning that the universal machine can perform any possible computation.  This power in turn has fuelled the information processing hypothesis – that cognition is symbol manipulation – that is at the heart of classical cognitive science.

References:

1. Hodges, A. (1983). Alan Turing: The Enigma Of Intelligence. London: Unwin Paperbacks.
2. 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)