Conway’s 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. 

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

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

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

---