next up previous contents
Next: Graph theory and Up: History Previous: The vocabulary of

Probability theory

The enthusiasm which greeted Martin Gardner's exposition of Life was initially focussed on tracing evolutions of two-dimensional configurations that struck one's fancy, or in trying to design configurations which would have some interesting characteristic. The original challenge was to either produce a configuration that would grow without limit, or to demonstrate that none existed. Conway proposed two mechanisms, a glider gun or a puffer train and examples of each were soon found -- contrary to his expectations in spite of having conjectured them, apparently.

However, as David J. Buckingham [18] remarked is his Byte article, interest eventually turned to information-theoretic aspects of automata theory -- something which would probably surprise anyone not familiar with this branch of engineering (or mathematics.) Even from the beginning, there was attention paid to the stastical properties of Life , Martin Gardner having reported some results of Robert Wainwright on the behaviour of "primordial soups" and their eventual evolution at fairly constant density [43, p. 237,].

Indeed, any prolonged observation of a Life field leads to the conclusion that there are three phases of evolution: The first phase is a relatively short transient phase -- at most ten or tens of generations -- in which excessively high or low initial densities adjust themselves; the second phase may last for thousands of generations in which nothing seems to be definite; followed by the third and final phase in which isolated groups of cells go through predictable cycles of evolution.

Simple ideas of probability yield approximately correct but undeniably discrepant results. The evident explanation that assumptions about independence and exclusivity -- after all, if the neighborhoods of two adjacent cells overlap by 50% or more, their evolutions might not be independent -- identifies the likely source of error, but says little about what to do about it. M. Dresden and D. Wong [35] made some probabilistic calculations concerning the evolution of Life in 1975; L. S. Schulman and P. E. Seiden [102] slightly later in 1978.

It has recently become apparent that old ideas about probability nests, quite highly developed in other branches of mathematics, are ideally suited to contending with this problem. It is a theory which can be especially well developed for one dimensional systems; W. John Wilbur, David J. Lippman and Shihab A. Shamma [116], then Howard A. Gutowitz, Jonathan D. Victor and Bruce W. Knight [51] have all published interesting results using these techniques.

Not only has there been considerable interest in resolving the statistical properties of cellular automata, there is a very definite current running in the opposite direction, by which known automata are taken as the starting point for exploring the statistics of other systems whose rules of evolution are much complicated. In this way one returns to Poincaré's views of approximating the properties of a dynamical system. The underlying hope is that valid statistical conclusions will arise from dynamical systems that are much simpler than those governed by differential equations.

Regarding a discretized differential equation as a cellular automaton is too much of a simplification unless the cells have a rather large number of states; still there are some significant aspects of nonlinear systems which can be modelled by relatively small automata. In one well studied case, three characteristic regions are recognized for the variable governed by a differential equation --- quiescent, active, and transitional.

Such a system is usually quiescent; but an activity can be initiated which must proceed to completion before calm can be restored; especially in two or more dimensions some interesting self-sustaining activation chains can be found, which have been taken as models of chemical or neurological behavior [46,76].



next up previous contents
Next: Graph theory and Up: History Previous: The vocabulary of



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