Example 2 Conways Life

Perhaps the most widely known C A is the game of Life, invented by John H. Conway, and popularized extensively by Martin Gardner in his Mathematical Games department in Scientific American in the early 1970s (see, for example, [gardnei 70]). 

One of the ino.st intriguing patterns in Life is an oscillatory propagating pattern known as the glider. Shown on the left-hand-side of figure 1.5, it consists of 5 live cells and reproduces itself in a diagonally displaced position once every four iterations. 

What is remarkable about this very simple appearing rule is that one can show that it is capable of univer.sal computation. This means that with a proper selection of initial conditions (i.e. the initial distribution of live and dead cells). Life can be turned into a general purpose computer. This fact fundamentally limits the overall predictability of Life s behavior. 

Put another way, this means that if you want to predict Life s long-term behavior with another model or by using, say, a partial differential equation, you 

---

Rules for which A is near Ac appear to support propagating solitoii structures, suggesting that the most complex rules (i.e. those belonging to Wolfram s class c4) lie within this transition region - A for Conway s Life rule, for example, is equal to 0.273 and lies within the transition region for k = 2, A/ = 9 two dimensional CA,... 

An early study of a stochastic CA system was performed by Schulman and Seiden in 1978 using a generalized version of Conway s Life rule [schul78]. Though there was little follow-on effort stemming directly from this particular paper, the study nonetheless serves as a useful prototype for later analyses. The manner in which Schulman and Seiden incorporate site-site correlations into their calculations, for example, bears some resemblance to Gutowitz, et.ai. s Local Structure Theory, developed about a decade later (see section 5.3). In this section, we outline some of their methodology and results. 

The idea that localized partic le-like propagating structures can be defined on a lattice Wcus nothing new. For example, Minsky was well aware of the existence of gliders in Conway s Life rule. Minsky s own pedagogical example was effectively a four-state one-dimensional CA with states a e 0,1,a,/ and rules 4> (cri i,CTi,cri+i) —cr given by ... 

For example, see D. E. Erwin. The Goldilocks Hypothesis [review of S. Conway Morris s Life s Solution Inevitable Humans in a Lonely Universe], Science, 302 (2003), 1682-3. 

Cellular automata have substantially furthered our understanding of complex systems. John von Neumann s self-reproducing automaton , and John Horton Conway s game of Life are perhaps the most widely known examples of cellular automata showing complex behavior on the basis of surprisingly simple local rules. Local rules, after all, are the prefered modus operand of nature. Besides, cellular automata are also a prototype.of the scientific quest to model the complicated by the simple. 

---