University of Alberta Dictionary of Cognitive Science: Computable Functions

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. The Turing machine was invented and used to prove that there exist some functions that are not computable (Turing, 1936). However, the subset of functions that are computable is large and important (Hillis, 1998). “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 20^th 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).

References: