- The organization of the remainder of the paper is as follows. We begin in Section 2 by reviewing our current understanding of Threshold Growth, monotone solidification models for which a reasonably complete thoery is available. The limit (#) holds in full generality, there is an explicit formula for the asymptotic L in terms of the system's threshold, and subtler issues of nucleation from small seeds can be analyzed in some detail. For comparison with more general models, let us state the basic Shape Theorem in some detail:
- The Shape Theorem. For Threshold Growth on a Box neighborhood, starting from any finite initial seed A0 which fills the lattice eventually,
- (i) the occupied set An spreads out linearly in time;
- (ii) n -1An attains a limiting shape L ;
- (iii) L is independent of the initial seed A0 ;
- (iv) L is convex;
- (v) L is a polygon.
- We will describe three methods of proof: direct recursion, which can be used for rules with small range; convex analysis, which describes L as a certain polar transform (Wulff shape, cf. [TCH] ); and the more robust subadditivity approach, which applies to a great many monotone spatial systems, but yields only an implicit representation of the asymptotic shape. A simple extension shows that monotone growth models obey the same theorem, with the same limit L, independent of their survival threshold. The section concludes with a brief discussion of nucleation questions: which small seeds manage to grow and which do not.
- In Sections 3-6 we present a series of examples to demonstrate that in CA growth models which are nonmonotone, any and all of (i) - (v) above may fail. Since cellular automata are capable of universal computation, any kind of growth can be concocted within the general CA framework. However this observation is of little use in understanding how items (i) - (v) fare within our rather restrictive class of growth models. Section 3 begins an exploration of arguably the simplest nonmonotone rules on the Moore neighborhood. We first examine Biased Voter Automata, growth models having arbitrary birth and survival thresholds, in which case more exotic scenarios such as concentric rings and
nonconstant limiting density profiles arise. We then turn to Exactly b Growth Automata in which a site is permanently added to the occupied set the first time it has exactly b occupied neighbors. For b=1 we find that starting from a singleton, a crystal with oscillating von Koch type boundary evolves. In particular, (#) only holds along suitable subsequences, with a continuum of distinct limits. The case b=2 provides another example of CA growth with complex boundary dynamics. It is easy to check that any 2 by n box grows, but apart from the 2 by 2 case one must resort to computer realizations in order to investigate the apparent limit L and whether it fills a Diamond.
- Section 4 treats the Exactly 3 CA, one of the most exotic of all growth rules, which generates remarkable complexity but seems amenable to some interesting experimental mathematics. This is Conway's Game with no 1 to 0 transitions, so it is called Life without Death (LwoD). One encounters dendritic "icicle" growth patterns that produce a seemingly stochastic mix: chaotic crystalline lava, horizontal and vertical ladders which evolve by a kind of weaving pattern and seem to outrun the surrounding lava, and parasitic shoots which emerge from the lava but can only race along the edges of stalks. The resulting interactions give rise to extensive self-organization in which very large regions of the growing crystal are repeatedly cloned exactly in time. As an indication that LwoD can be analyzed mathematically, we will prove one result which captures its sensitive dependence on initial conditions. Namely, given any finite initial configuration A0, one can produce perturbations differing at only 28 sites, one of which grows persistently whereas the other fixates. At present, apart from minor variants, we know of no other CA rule with this property. The ability of LwoD to emulate arbitary Boolean circuits is also discussed briefly.
- Next, in Section 5, we turn to solidification automata in which a birth occurs if either b or b' of the 8 neighbors are occupied. Various rules with b = 2 and 3 produce "counterexamples" to several parts of the Shape Theorem. Recursive dynamics establish that the limit L can depend on the initial seed A0, and be nonconvex in certain cases. Computer experiments seem to suggest that other examples have polygonal asymptotic shapes even though their boundary dynamics are chaotic. But one must be quite careful in reaching conclusions based on visualization - sometimes the crystal appears polygonal for the first several hundred updates, but later is more suggestive of a shape with smooth boundary.
- Section 6 presents empirical case studies for three of the most intriguing CA growth models of all. Wolfram's Circle is the nearest neighbor totalistic rule which seems to do as good a job as any of spreading like a circle. We present numerical data concerning the first several thousand updates of its evolution from a small lattice circle, interpreting the results in the context of the general isotropy problem for local spatial growth dynamics. Next, we turn to Conway's Life. This celebrated CA continues to be studied intensively after more than 25 years of avid experimentation and analysis. Indeed, there have been major breakthoughs in the design of recursive organizing seeds for Life within the past few years. Still, many of the most basic ergodic properties of the rule remain a mystery. We sketch the current state of knowledge, with an emphasis on growth-related issues. Our third gem is Hickerson's Amoeba, the most volatile CA growth model we know. Although its dynamics are interfacial, we will exhibit arbitrarily large seeds from which this CA dies out completely, whereas experiments show that very small perturbations of even the smallest seeds of the same design can grow to fill an array several thousand cells on a side. One thus suspects that persistent growth is possible. Boundary shocks are so catastrophic, however, that the prospects for a limit shape L remain decidedly murky.
- Finally, in Section 7 we present a brief overview of stochastic growth: in cellular automata which evolve from random initial states, and also for processes which evolve randomly. With deterministic updating, chance enters the picture when we start from a random set, e.g. from the Bernoulli product measure which occupies each site independently with probability p. Such CA rules from random initial states are stochastic processes, albeit degenerate, and are among the most mathematically tractable prototypes for various nonlinear spatio-temporal phenomena. For random spatial dynamics such as interacting particle systems [Lig], [Dur], problems of asymptotic shape have played a central role since Eden's crystal growth model [Ede] and Broadbent and Hammersley's first-passage percolation [BH] were introduced in the late 1950s. The boundary interface of even the simplest random dynamics exhibit complex fluctuations, making explicit determination of L exceedingly difficult. Thus subadditivity is often the only available technique for proving shape theorems. Until now, some variant of additivity has been a key assumption. We describe a new result of type (#), due to Bohman and Gravner [BG], for randomized CA dynamics knows as Stochastic Threshold Growth. The key ingredient in the analysis of these nonlinear sytems is a deterministic combinatorial lemma which extends the regularity theory for Threshold Growth CA models recently developed by Bohman [Boh]. Finally, we show how it is possible to estimate L efficiently by Monte Carlo simulation, and thereby present evidence for an intriguing convexification transition as the random component of the dynamics increases.
- Numerous problems are posed throughout the paper; some are intended as exercises, others as avenues for further research. Also, our introductory discussion makes it clear that computer calculation and visualization play an indispensible role in the study of cellular automaton growth. The paper concludes with an Appendix listing additional electronic resources available to the reader: an asssortment of links to the World Wide Web, downloadable software programs, and a library of companion CA experiments for this research, available on various platforms.