# Cellular Automata with Global Control

Posted to the NKS Forum
October 14, 2003

Read Forum Thread

I was having dinner this evening with Paul Davies, and we
ended up doing a *Mathematica* experiment that I thought people on
the Forum might be interested in hearing about.

Paul's work on astrobiology had led him to wonder whether perhaps living
systems might be characterized by having rules that somehow depend on
global features of their state.

I suggested that we try a little experiment to look at some minimal pure
NKS systems with this property.

The idea was to have a system in which there are two possible cellular
automaton rules, with the first rule being applied at a given step if the
total number of black cells at that step is even, and the second rule
being applied if the total number of black cells is odd.

In *Mathematica*, the evolution function is then:

GCA[{r1_, r2_}, init_, t_] :=

NestList[CellularAutomaton[{r1, r2}[[Mod[Total[#], 2, 1]]], #,

1, {-1}][[1]] &, init, t]

(Note that this uses the *Mathematica* 5 function `Total`

.)
Now define (this is rather klunky, but it is what I wrote at dinner, so I
reproduce it here):

AllCases[list_] :=

Union[Sort /@

Flatten[Outer[List, ##] & @@ Table[list, {Length[list]}],

Length[list] - 1]]

and

RasterGraphics[list_] := Graphics[Raster[Reverse[1 - list]], AspectRatio -> Automatic]

Then start looking at things like:

Show[GraphicsArray[{RasterGraphics[

GCA[#, ReplacePart[Table[0, {200}], 1, 100], 200]] & /@

AllCases[{30, 150}]}]]

The middle of these three pictures shows the result of "mixing" rules 30
and 150. It's a somewhat interesting "decorated" nested pattern.

An obvious question is: are there rules where each individual rule is
simple, but the combination is not.

I started doing an exhaustive search. Quite soon we saw the case
{11, 28} — i.e. the combination of rules 11 and 28.

Starting from a single black cell it produces a rather remarkable pattern.
There is considerable randomness, but there are strange patches and bursts
of order.

There is a background of stripes, with a black stripe occuring whenever
rule 11 gets applied after rule 28.

We tried to figure out whether there was regularity in this background.
There did not seem to be. The frequency of stripes seemed, however, to
converge to about 0.28, with fluctuations following roughly a random
walk.

We then looked at what happens with random initial conditions. With an
even width of system, randomness seems to persist. But with an odd width,
it usually seems to die out rapidly, leaving distinctly class 2
behavior.

That was as far as we got in the half hour or so that we spent on this.

There are several obvious things to do.

First, finish the exhaustive search. Perhaps start by looking just at the
16 k=2, r=1/2 rules, and see if any combinations of them lead to
interesting behavior.

Next, try to analyse the {11, 28} case more carefully. Look at
difference patterns with random initial conditions. Look at various
simple initial conditions, seeing how much effect they have on the final
pattern produced.

We noted a few other cases that looked interesting: {14, 22},
{14, 28}, {17, 28}, {18, 28}, {22, 25}.

How common is class 4 behavior in these globally-controlled rules?

What happens with other forms of global control? In which one chooses the
rule on the basis of other quantities, say as discussed in the NKS book,
page 1022R.

I'm not sure to what extent this will all illuminate Paul Davies's
original question—on which I have definite views, as expressed in
Chapter 12. But I think cellular with global control are interesting
systems that deserve to be studied, and will no doubt have interesting
applications.

Attached is a picture of the {11, 28} case, as well as the raw
notebooks [1 | 2] we generated. (The first notebook I quit after
it got to 129 megabytes in size.)