next up previous
Next: The evolution of Up: What has been Previous: What has been

The concept of an automaton

Whether or not the ideas of McCulloch and Pitts have any bearing on neurophysiology, there is no doubt that their proposals stirred up a considerable amount of interest, some of which can fairly be seen as having resulted in the present theory of automata. Indeed, von Neumann made quite direct and extensive reference to their ideas in the process of designing the EDVAC as well as in his work on self reproducing automata.

Another direct outgrowth of their work was origin of the theory of regular expressions, which was formulated by Stephen Kleene[45] as a rigorous logical and algebraic foundation for their ideas. In turn, regular expressions have been found to lie at the foundation of the theory of formal languages; indeed they constitute just about the simplest of all languages, because the others always include them. This is a subject which can be pursued in great detail, but which is not strictly a part of the theory of cellular automata. Nevertheless the circle closes when it is found that regular expressions are invaluable for describing paths through graphs, one of the preferred representations by which the evolution of cellular automata may be described.

All of these early ideas have undergone extensive development since they were first proposed. To start with, von Neumann was deeply involved with a critical phase in the development of computers, which coincided with his interest in cellular automata. As a mathematician he had an interest in symbolic logic and the theory of computation which permeated his approach to computer design. Setting out to equip a computer with the organs required to realize a certain philosophy of computation is a rather different proposition from uncovering all the capabilities of a complex circuit which one has designed.

The logical issues which preoccupied von Neumann would not have concerned all designers, nor did he necessarily cast computer design into a mold which would not otherwise have shaped it. Nevertheless decisions ranging from the choice of the binary number system to the systematic use of stored programs evolved during that formative era. Previously computers had not been complex enough to make the issues important, although Ada Lovelace touched on some of the points in her description of Babbage's Analytical Engine; subsequently computers worked well enough and were sufficiently well understood that after 1956 or thereabouts they tended to be copied rather than redesigned as they went into commercial production.

Another direction which the early ideas took was the growth of the general theory of automata as well as the study of formal languages. In fact the McCulloch-Pitts ``neurons'' were only one example of digital circuitry, as distinguished from analog circuitry; naturally the use of such circuits required a theory to explain them. Boolean algebra served for combinatorial circuits; the incorporation of memory elements or time delay elements extended the theory to take into account sequential circuits, the kind that could be used in computing machines.

General automata differ from cellular automata in two important respects. Ordinary automata are concerned with input and output, that is, the transformation of signals through the intervention of the automaton. Moreover, design problems are typically concerned with constructing the precise automaton which will produce a given transformation, ascertaining the possible equivalence of two automata in their signal handling abilities, finding the simplest automaton for a given purpose, and so on. The second characteristic is that they are typically small, in any event finite, being intended for use in actual construction.

In contrast cellular automata are required to form lattices, infinite in principle if not in practice, and do not work with signals. Rather, the ``signal'' which activates each cell is its knowledge of its own state and the states of a certain number of its neighbors at any given moment. Were the lattice not infinite, there would be no discussion of Turing machines, universal computation, or the like. On the other hand, just because of its large scale regularity, a cellular automaton lends itself readily to implementation in terms of microelectronics.

In any event, it could hardly be expected that it would be possible to discuss cellular automata without first taking a certain amount of the general theory into account.



next up previous
Next: The evolution of Up: What has been Previous: What has been



Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx