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


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

Then start looking at things like:

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

Picture of the {11, 28} case—click to enlarge
Click to enlarge

Publications by Stephen Wolfram »