Cellular automata are but a specialized instance of the general theme of automata theory; the difference lies in the fact that automata are driven by input signals and produce output signals. Cellular automata enjoy all the symmetries, mostly translational, inherent in their crystallographic layout; but they use the states of selected neighbors for input signals and are not generally considered to produce output.

Automata theory itself has an ancient history, if one thinks of automata as mechanisms capable of performing intricate movements; but if the actual apparatus is discarded in favor of the activity itself, such a theory more properly begins with the neurophysiological abstractions of McCulloch and Pitts. Their refinement into the theory of regular expressions by Kleene constitutes one of several viewpoints, which have gone on to include semigroups (or monoids) of mappings of a set into itself, or even the theory of grammars.

The semigroup aspect has been exploited by Kenneth Krohn and John L. Rhodes [68]; that was followed up with monoid theory by Samuel Eilenberg [38,39]. Semigroup theory is much more intricate than the theory of groups, whose classification has been one of the more important mathematical accomplishments of recent times; but a general knowledge of the principles involved is still very useful for automata. These principles include the definition of one sided and two sided ideals, and their use to give a semigroup a standard structural form.

The grammatical approach is primarily a creation of the MIT linguist Noam Chomsky [20,21,22,23], referring primarily to the sequence of transformations which a system can undergo. The emphasis is more on characterizing a set of symbolic equations describing the transformations, than on the transformations themselves, which is the province of semigroup theory. The details to be resolved consist principally in establishing the existence and possibly the uniqueness of the solutions.

The decades of the fifties, sixties, and into the seventies, saw a tremendous amount of research on automata, languages, and similar topics; cellular automata as such were not given much special attention, although sometimes they were utilized as examples or illustrations.

Some of the themes treated, although not necessarily unique to cellular automata, but often emphasizing one dimension, were the ``busy beaver'' problem in which long lasting activity from simple initial configurations was sought, the ``firing squad'' problem in which evolution to a specified configuration was the goal, or the ability to achieve ``universal computation'' via the emulation of a Turing machine.

E-mail:mcintosh@servidor.unam.mx