A universal machine is a device that is maximally flexible in two senses (Newell, 1980). First, its behavior is responsive to its inputs; a change in inputs will be capable of producing a change in behavior. Second, a universal machine must be able compute the widest variety of input-output functions that is possible. This “widest variety” is known as the set of computable functions. A device that can compute every possible input-output function does not exist. “It can be proved mathematically that there are infinitely more functions than programs. Therefore, for most functions there is no corresponding program that can compute them. ... Fortunately, almost all these noncomputable functions are useless, and virtually all the functions we might want to compute are computable (Hillis, 1998, p. 71).
A major discovery of the 20th century was that a number of seemingly different symbol manipulators were all identical in the sense that they all could compute the same maximal class of input-output pairings (i.e. the computable functions). Because of this discovery, these different proposals are all grouped together into the class “universal machine”, which is sometimes called the “effectively computable procedures”. This class is “a large zoo of different formulations” which includes “Turing machines, recursive functions, Post canonical systems, Markov algorithms, all varieties of general purpose digital computers, most programming languages” (Newell, 1980, p. 150). Newell (1980) proved that a generic physical symbol system was also a universal machine. This proof, coupled with the physical symbol system hypothesis, leads to a general assumption of classical cognitive science: cognition is computation, the brain implements a universal machine, and the products of human cognition belong to the class of computable functions.
- Hillis, W. D. (1998). The Pattern on the Stone (1st ed.). New York: Basic Books.
- Newell, A. (1980). Physical symbol systems. Cognitive Science, 4, 135-183.
(Added September 2010)