- Although Conway's Game of Life and some of its variants have been studied extensively since the 1970's, the first systematic empirical investigation of nearest-neighbor totalistic CA rules was carried out during the early 1980's in a series of influential papers by Wolfram [Wol1] which dealt mainly with one-dimensional systems. For our purposes, the most relevant reference is a fascinating experimental survey of two-dimensional cellular automata by Packard and Wolfram [PW] from 1985. They called the 218 Moore neighborhood rules we have introduced above outer totalistic, labeling them by means of a rather uninformative indexing scheme. For instance, Conway's Life is Rule 224. We will choose more descriptive names for the CA rules discussed here. Among the provocative findings in [PW] are this summary of the shapes observed:
- Most two-dimensional patterns generated by cellular automaton growth have a polytopic boundary that reflects the structure of the neighborhood in the cellular automaton rule. Some rules, however, yield slowly growing patterns that tend to a circular shape independent of the underlying cellular automaton lattice.
- this concerning dependence on the initial configuration:
- ... the growth dimensions for the resulting patterns are usually independent of the form of the initial seed. ... There are nevertheless some cellular automaton rules for which slightly different seeds can lead to very different patterns.
- and this on CA complexity:
- Despite the simplicity of their construction, cellular automata are found to be capable of very complicated behavior. Direct mathematical analysis is in general of little utility in elucidating their properties.
- In keeping with this last sentiment, nowhere in [PW] do the authors explain exactly what is meant by a growth rule or its asymptotic shape. Nor do they offer any compelling evidence for the claim that CA growth can become increasingly circular. In order to discuss such intriguing phenomenological issues, it is illuminating (and reasonably straightforward) to adopt a precise framework and terminology for systems which evolve from a finite initial set A0 of occupied sites.
- For maximum flexibility, we will call An a growth model as long as b(0)=0, in which case 1's cannot appear spontaneously in a sea of 0's, instead arising only by local contact with other occupied cells. In case s(N-1)=1, so that 0's can only arise by interaction at the edge of the growth cluster, we say that An is an interfacial growth model. Particularly simple are the solidification models with s identically 1, in which case any site is permanently occupied once a birth occurs there. Two additional structural properties facilitate mathematical analysis. First, as already mentioned, a few cellular automata are additive (linear), meaning they satisfy a superposition property. Examples are the xor process and the or process. A larger, but still quite restrictive class of automata are monotone (attractive), meaning that set inclusion is preserved by the update rule T. Note that CA growth models are monotone if and only if b and s are both non-decreasing and b < s.
- The notion of limiting shape is easiest to conceptualize for solidification models. In this case the state may change at most once at each site, so the dynamics have a limit. Of course this asymptotic configuration may be some finite final crystal (fixation), or conceivably some complex infinite dendritic formation. But one expects most rules capable of growth (roughly, the "supercritical" ones) to fill Z2 in an orderly fashion, and to spread out linearly in time with a characteristic shape when started from sufficiently large (again, "supercritical") seeds. With this scenario in mind, we say that a CA has asymptotic shape L started from A0 if
(#)n -1An converges to L
- (in the Hausdorff metric: every point in the converging set is eventually within distance h of L, and vice versa.) Of course there is no guarantee that the occupied set of a particular CA will spread at a linear rate, or even if it does that the geometry of its growth will converge in this sense, but such behavior is widely observed in computer experiments and confirmed by the rigorous results for Threshold Growth and other tractable rules to be discussed in this paper. New complications arise when we attempt to formulate shape results for models in which occupied sites can become empty. Even in well-behaved dynamics, one then expects the occupied region to exhibit a dynamic "pattern" as it spreads. As long as this pattern has positive density, a limiting L may still be expected to exist, but will capture only the shape of the growth, not its characteristic density. We will formulate a refinement which incorporates a density profile when this issue arises in Section 3.