Turing Machines (TMs) can be seen and studied mathematically as lists of instructions, without any mechanical counterpart. But they can also be seen as a type of computing mechanism, which is made out of a tape divided into squares and a unit that moves along the tape, acts on it, and is in one out of a finite number of internal states (see Davis et al. 1994 for more details). The tape and the active unit are the components of TMs, whose functions are, respectively, storing symbols and performing operations on symbols. The active unit of TMs is typically not further analyzed, but in principle it may be functionally analyzed as a Boolean Circuit plus a memory register. When they are seen as mechanisms, TMs fall naturally under the functional account of computing mechanisms. They are uniquely identified by their functional analysis, which includes their list of instructions.
There are two importantly different classes or TMs: ordinary TMs and universal TMs. Ordinary TMs are not programmable and a fortiori not universal. They are “hardwired” to compute one and only one function, as specified by the list of instructions that uniquely individuates each TM. Since TMs’ instructions constitute full-blown algorithms, by the light of the present analysis they are special-purpose computers.
Universal TMs, on the other hand, are programmable (and of course universal), because they respond to a portion of the symbols written on their tape by computing the function that would be computed by the TM encoded by those symbols. Nevertheless, universal TMs are not stored-program computers, because their architecture has no memory component—separate from its input and output devices—for storing data, instructions, and results. The programs for universal TMs are stored on the same tape that contains the input and the output. In this respect, universal TMs are analogous to early punched cards computers. The tape can be considered an input and output device, and with some semantic stretch, a memory. But since there is no distinction between input device, output device, and memory, a universal TM should not be considered a stored-program computer properly so called, for the same reason that punched cards machines aren’t.
Even after the invention of TMs, it was still an important conceptual advance to design computers that could store their instructions in their internal memory component. So, it is anachronistic to attribute the idea of the stored-program computer to Turing (as done, e.g., by Aspray 1990 and Copeland 2000a). This exemplifies how a proper understanding of computing mechanisms, based on functional analysis, can shed light on the history of computing.
4Application 2: A Taxonomy of Computationalist Theses
Computing mechanisms have been employed in computational theories of mind and brain. These theories are sometimes said to be metaphors (Eliasmith 2003), but a careful reading of the relevant works shows that computationalism is a literal mechanistic hypothesis (Piccinini 2003c, forthcoming b). The functional account of computing mechanisms can be used to add precision to computationalist theses about the brain by taxonomizing them in order of increasing strength. The theses range from the commonsensical and uncontroversial thesis that the brain processes information to the strong thesis that it is a programmable, stored-program, universal computer. Each thesis presupposes the truth of the preceding one and adds a further assumption to it:
The brain is a collection of interconnected neurons that deal with information and control (in an intuitive, formally undefined sense).
Networks of neurons are computing mechanisms.
Networks of neurons are Boolean circuits or finite state automata (McCulloch and Pitts 1943).27
The brain is a programmable computer (Devitt and Sterelny 1999).
The brain is a programmable, stored-program computer (Fodor 1975).
The brain is a universal computer (Newell and Simon 1976).28
Thesis (1) is sufficiently weak and generic that it entails nothing controversial about neural mechanisms. Even a non-cognitivist (e.g., a behaviorist) should agree on this. I mention it here to distinguish it from nontrivial computationalist theses and leave it out of the discussion.
Historically, thesis (3) is the first formulation of computationalism. Its weakening leads to (2), which includes modern connectionist computationalism. Its strengthening leads to what is often called classical (i.e., non-connectionist) computationalism. Classical computationalism is usually identified with (5) or (6), but sometimes (4) has been discussed as an option. The above taxonomy allows us to see that different formulations of computationalism are not equivalent to one another, and that they vary in the strength of their assumptions about the functional properties of neural mechanisms.
The above list includes only the theses that have figured prominently in the computationalist literature. This list is by no means exhaustive of possible computationalist theses. First, notice that (3) can be divided into a relatively weak thesis—according to which the brain is a collection of Boolean circuits—and a much stronger one—according to which the brain is a collection of finite state automata. The functional account of computing mechanisms shows how to construct theses that are intermediate in strength between these two. For instance, one could hypothesize that the brain is a collection of components that can execute complex pseudo-algorithms (i.e., effective procedures defined only on finitely many inputs of bounded length), like the multiplication and division components of modern computers.
Another possible version of computationalism is the hypothesis that the brain is a calculator. This possibility is intriguing because no one has ever proposed it, even though calculators are bona fide computing mechanisms. The functional account of computing mechanisms sheds light on this fact. Among other limitations calculators have, the computational repertoire of calculators is fixed. There is no interesting sense in which they can learn to compute new things or acquire new computational behavior. One important factor that attracted people to computationalism is the flexibility and power of computers, flexibility and power that calculators lack. Because of this, it is not surprising that no one has proposed that brains are calculators.
The kinds of computers that are most strongly associated with computationalism are programmable, stored-program, universal computers, because they have the exciting property that given appropriate programs stored inside the machine, they can automatically compute any computable function, and they can modify their programs automatically (which gives them an important kind of learning ability).