next up previous
Next: Still life Up: Life 's Still Previous: Introduction

Cellular automata

Mathematically, an automaton consists of a set of states, together with a set of mappings of the state set into itself. Each mapping is identified with a signal, which is supposed to cause a change of state. Signals can therefore be considered as inputs to the automaton, which in turn could be considered as a neural net, an electronic circuit, or some other structure. In that case, outputs might also considered, and altogether the groundwork has been laid for some kind of fundamental theory of computation, or at least of computing devices. Much of the theory of automata procedes in that direction.

Cellular automata are those for which a large number of similar automata---the cells---are connected together in some regular pattern, and for which the signals are the information which each cell has concerning some of its neighbors, most likely including selfawareness. From time to time the cells change their state, according to this knowledge. McCulloch and Pitts would have the connectivity of the cells modelling some physiological system, but lacking definite structures to follow, the tendency has been to use crystallographic lattices of low dimension. Von Neumann worked with two dimensions, which was also the arena for Conway's game.

Life presupposed binary cells occupying a two dimensional square lattice, the neighborhood of each cell consisting of itself, four lateral neighbors, and four diagonal neighbors; a total of nine cells altogether. Many other combinations are possible, but Conway chose one of them, as well as a particular rule of transition, for his game after discarding many alternatives. Adopting his picturesque ecological metaphor, binary cells are either dead or alive; in each generation,

There are , or 512, different combinations of dead and live neighbors. Each combination can evolve in its own way, giving the enormous number of different rules, or games, which Conway could have chosen; nevertheless that one choice has lived up to his expectations of finding an interesting game. Part of the choice consisted in selecting a symmetric rule; it is reasonable to suppose that a square lattice would evolve similarly if it were rotated or reflected, as well as if any configuration were shifted to on side by a given distance. Beyond this, the rule depends on numbers of live neighbors, not on particular groupings.

Whatever the reasons for choosing one rule in preference to another, the analysis which follows is applicable to all cellular automata; so Life just happens to be a particularly interesting special case. Consequently its results are available for comparison and checking against other rules.



next up previous
Next: Still life Up: Life 's Still Previous: Introduction



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