Conways Life Rule

Perhaps the single most studied (and joyfully played with) rule - certainly the most famous is the two-dimensional Moore neighborhood binary-valued CA invented by John H. Conway, and popularized extensively by Martin Gardner in his Mathematical Gaines column in Scientific. American in the early 1970 s ([gardnerTO], [gardnerTl], [gardner78]). 

Conway, aware of Fredkin s and Ulam s rules defined in the preceding section, wanted to create a rule that would be both as simple to write clown and as difficult to predict the behavior of as possible. To this end, Conway concentrated on meeting the following three cu iteria  

There should not exist simple initial patterns that obviously grow without limit it should be difficult to prove tliat an arbitrary pattern grows forever. 

There should exist simple patterns that give the appearance of growing forever not all simple initial states should inmiediately yield trivial final states. 

There should exist simple patterns that evolve for many iterations before. settling into a simple (either stable or oscillatory) final static 

---

While a single vant performs little more than a pseudo random-walk, multiple-vant evolutions are ripe with many interesting (Conway Life-rule-like) patterns, particularly when the background lattice food color is shown along with the moving... 

Conway Introduced two-dimensional cellular automaton Life rule... 

Chapter 7 discusses a variety of topics all of which are related to the class of probabilistic CA (PCA) i.e. CA that involve some elements of probability in their state and/or time-evolution. The chapter begins with a physicist s overview of critical phenomena. Later sections include discussions of the equivalence between PCA and spin models, the critical behavior of PCA, mean-field theory, CA simulation of conventional spin models and a stochastic version of Conway s Life rule. 

The simplest binary valued CA proven to be computation universal is John Conway s two-dimensional Life rule, about which we will have much to say later in this chapter. Many of the key ingredients necessary to prove universality, however, such as sets of propagating structures out of which analogs of conventional hardware components (i.e., wires, gates and memory) may be explicitly constructed, appear, at least in principle, to be supported by certain one-dimensional rules as well. The most basic component required is a mechanism for transporting localized packets of information from one part of the lattice to another i.e., particle-like persistent propagating patterns, whose presence is usually indicative of class c4 behavior. 

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,... 

The formal study of CA really began not with the simpler one-dimensional systems discussed in the previous section but with von Neumann s work in the 1940 s with self-reproducing two-dimensional CA [vonN66]. Such systems also gained considerable publicity (as well as notoriety ) in the 1970 s with John Conway s introduction of his Life rule and its subsequent popularization by Martin Gardner in his Scientific American Mathematical Games department [gardner83] (see section 3.4-4). 

Fig. 3.69 A sampling of period-two patterns under Conway s Life rule.

Sketch of a Proof that Conway s Life-rule is Universal... 

Perhaps the simplest way to prove that a system is capable of universal computation - certainly the most straightforward way - is to show that the system in question is formally equivalent to another system that has already been proven to be a universal computer. In this section we sketch a proof of the computational universality of Conway s Life-rule by explicitly constructing dynamical equivalents of all of the computational ingredients required by a conventional digital computer. 

Bayes, in a series of papers, ([bayes87a], [bayes87b], [bayes88], [bayesQO], and [bayesQl]) has searched for three-dimensional analogs of Conway s Life-rule that are worthy of the name [dewd87],... 

A three-dimensional analog of a Conway object is then defined to be an expansion sucli that, when subjected to the appropriate three-dimensional Life-rule, yields after each and every generation a projection that is identical to the original Conway object for the same iteration step under Conway s original two-dimensional... 

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. 

Although, just as for Conway s Life rule, static displays simply cannot do justice to the dynamical patterns that (unerge in the course of a typical vant evolution, figures 11.8 and 11.9 show a few snapshot views. Note that, in both figures, the lattice initially contains only yfsllow food and a site is colored black whenever it contains either green food or a vant of either color. 

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 ... 

---