89

This region of the map deals with general mathematical properties of machines, rather than with the specific architectural properties dealt with on the other maps.

Connectionist networks (see Map 5) and physical symbol systems (see Map 3), for example, are automata, because they implement effective processes that are Turing computable.

Turing Machines

The concept of a Turing machine arose in the context of attempts by mathematicians to specify precisely what an algorithm was.

Alan Turing's insight was that any algorithm could be carried out by one of a class of Turing Machines. Indeed, he proved that an algorithmic procedure that can be implemented by a device that blindly and deterministically manipulates symbols. So, Turing machines precisely define the concept of an algorithm.

A Turing machine is conceived of as an imaginary device that manipulates symbols on a tape. The behavior of a Turing machine is determined by the state it is in and by the symbol it reads on the tape. Based on those two factors, the machine will enter a new state, write a symbol on the tape, move to the right, or to the left, or halt.



The table of rules (or "machine table") correlating these reactions with states and symbols exhaustively specifies a given machine. Based on its machine table, we can determine exactly what a Turing machine will do with any given tape.

A "universal Turing machine" is a Turing machine that can perform all the calculations of any other Turing machine. To emulate a given machine, the Universal Turing Machine is "programmed" with a special tape that fully describes the emulated machine's table.

What is a Machine?

A great many notions of what a machine is are found in the literature. A machine is:

1) Any instantation of a formal system (Lucas, 1961, p.44).

2) Anything that can be effectively constructed (George, 1962, p.63).

3) Anything that operates according to an algorithm (Coder, 1969, p.235).

4) Anything constructed from "unconnected primordial parts" (Hartmann, 1935, p.71).

5) Anything equivalent to a Turing machine (various contemporary authors, including Searle 1991, Nelson 1989, and Benacerraf, 1967).

6) Anything that can be given a purely geometric description (Spinoza, 1674, p.129).

7) Anything that behaves accoridng to an unambiguous set of instructions that requires no imagination to follow (Crossley et at, 1972, p.32).

8) Any device generating a recursively enumerable set of integers (Webb, 1968, p.158).

9) Any device that is, in principle, divisible into parts (Lucas, 1961, pp.56-57).

10) Any system whose behavior can be fully explained in terms of proximate causation (Mayr, 1982, pp.67-70 and 114-16).

11) A system that obeys both principles of physical and chemical causality and principles of human functional design (Polyani and Prosch, 1975, pp.168-70).

Note: Other notions of what makes a machine are found in the historical literature. See, for example, Descartes, Kant, Newton, La Mettrie.