NKS Research Tools: CellularAutomaton

Richard Phillips, Wolfram Research Inc.,

richardp@wolfram.com
24th April 2004

Introduction

CellularAutomaton is a built in part of Mathematica

Mathematica is an integrated environment for technical computing, and doing technical work generally.

It is one system built on the unifying principle of symbolic programming, which is the perfect tool for dealing with the simple programs of NKS.

It is a single function, and it is very general

It is simple to use in simple cases.

It is also general purpose, and can work out any possible case.

It is very efficient

It can compute lots of steps quickly.

The internals use clever optimizations.

Represent the colors of cells using numbers

For 2 colors, say white and black, the convention is to use 0 and 1.

For k colors the convention is to use 0 to k-1.

It is possible to use other conventions but rarely necessary.

Represent arrays of cells using Mathematica lists

The following cells are represented as a list of 0s and 1s.

{0, 1, 0, 1, 1}

Multiple steps of the cellular automaton are also collected into a list

Multiple rows of cells are represented as an ordinary matrix:

{{1, 1, 0, 1}, {0, 0, 1, 1}, {0, 1, 0, 0}} // MatrixForm

Therefore the history of the evolution of a line of cells over many steps is just a matrix of numbers.

This is convenient since if the inputs and output are just lists and matrices, Mathematica can already deal with these things in lots of ways.

Most importantly for NKS...

Easy to set up and do experiments with it!

Easy to make changes and try various cases.

Graphics programs

RasterGraphics plots a matrix of numbers as colored cells.

RasterGraphics[state_?MatrixQ, colors_Integer : 2, opts___] := 
      Graphics[Raster[Reverse[1 - (state/(colors - 1))]], 
        AspectRatio -> (AspectRatio /. {opts} /. 
              AspectRatio -> Automatic), opts]

Basic examples for Elementary CAs

This is rule 30 run for 3 steps, from a single 1 on an infinite background of 0's.

CellularAutomaton[30, {{1}, 0}, 3] // MatrixForm

Show[
        RasterGraphics[CellularAutomaton[30, {{1}, 0}, 3]]];

This is rule 110 run for 5 steps, from a single 1 on an infinite background of 0's.

CellularAutomaton[110, {{1}, 0}, 5] // MatrixForm

Show[
        RasterGraphics[CellularAutomaton[110, {{1}, 0}, 5]]];

Specifying the inputs

One calls CellularAutomaton with either 3 or 4 arguments. If the forth argument is omitted the function assumes a default behaviour for the fourth argument.

CellularAutomaton[rule,startingCells,steps]

CellularAutomaton[rule,startingCells,steps,cellsToReturn]

I'll now look at each of these for one-dimensional rules.

First argument: Rule

Simplest case - the elementary CAs - just use an integer between 0 and 255

CellularAutomaton[integer,… ]

Show[
        RasterGraphics[CellularAutomaton[90, {{1}, 0}, 30]]];

Using more colors, but still considering the nearest neighbors.

CellularAutomaton[{integer,colors},… ]

Here is a 3 color nearest neighbor rule

Show[
        RasterGraphics[CellularAutomaton[{2067496389638, 3}, {{1}, 0}, 30], 
          3]];

We can use rules that depend on more than one neighboring cell too.

The third element of the list, which should be an integer, means to look at neighbors that many elements to the left or the right.

CellularAutomaton[{integer,colors,range},… ]

So the following form of neighborhood:

is achieved by using:

CellularAutomaton[{integer,colors,2},… ]

Show[
        RasterGraphics[
          CellularAutomaton[{2190937102, 2, 2}, {{1}, 0}, 10]]];

This rule grows twice as fast as a range 1 rule. That third argument is called the range. The number of cells in the neighborhood is just:
   2*range + 1

All these forms of argument will now cover all possible CAs, but as a convenience a further more complicated form is allowed too.

CellularAutomaton[{integer,{colors, weights},integer},… ]

What I have called the "weights" here, is just a list of integers (which may individually be zero).
A range 1 example will explain what this means:

CellularAutomaton[{integer,{colors,{w1,w2,w3}},1},… ]

If the cells in a neighborhood have values v1, v2, v3, then the new cell will have color:

Part[Reverse[IntegerDigits[integer,colors,colors^3]],1+w1*v1+w2*v2+w3*w3]

The weights colors^2, colors, 1 describe the most general possible set of rules, since each combination of the cell values picks out a different independent digit in the rule number. This is just Wolfram's standard numbering scheme for CAs described early on in the book [link].

In form of arguments without the weights is in fact just shorthand for these weights, which must be true since I said they we the most general rules too.

CellularAutomaton[{integer,{colors,{colors^2,colors,1}},1},… ] === CellularAutomaton[{integer,colors,1},… ]

The great thing about this framework is that the totalistic and outer-totalistic rules are easy to write in it. These are important subsets of the general class of all possible rules.

The range 1 totalistic rules are written:

CellularAutomaton[{integer,{colors,{1, 1, 1}},1},… ]

A useful allowed shorthand is:

CellularAutomaton[{integer,{colors,1},1},… ]

The range 1 outer-totalistic rules are:

CellularAutomaton[{integer,{colors,{colors,1,colors}},1},… ]

Another useful thing about this framework is that it allows us to specify rules that don't depend on the values of certain cells by giving a 0 for the corresponding weight.

Here are rules that depend only on the center cell and the left neighbor, but not on the right neighbor.

CellularAutomaton[{integer,{colors,{colors,1,0}},1},… ]

Second argument: Starting cells

There are two forms for this.

The first is for cyclic boundary conditions.

CellularAutomaton[rule,list,…]

Show[
        RasterGraphics[
          CellularAutomaton[2, {0, 0, 0, 1, 0, 0}, 8]]];

The second is for simulating infinite boundary conditions.

CellularAutomaton[rule,{list, background},…]

Show[RasterGraphics[CellularAutomaton[2, {{1}, 0}, 8]]];

We can also do cyclic background patterns:

Show[
        RasterGraphics[
          CellularAutomaton[30, {{1, 1}, {1, 0, 1, 1}}, 50]]];

And we can place groups of cells at specific positions in the infinite array:

Show[
        RasterGraphics[
          CellularAutomaton[30, {{{{1}, {-10}}, {{1, 1}, {20}}}, 0}, 
            50]]];

Third argument: Number of steps

This is very simple: just the number of steps for which we run the CA.

Typically the number of rows of the output matrix is this number plus one.  But that may not be true if we use the forth argument to return some rows and not others.

Length[CellularAutomaton[30, {{1}, 0}, 7]]

7 + 1 == 8

Optional fourth argument: Which cells to return

The optional forth argument is used to return only certain rows and column of the evolution array. Or in general only certain sub-arrays.

The most useful example of this is when we want only the last row:

First[CellularAutomaton[30, {{1}, 0}, 5, -1]]

First[CellularAutomaton[30, {{1}, 0}, 5, {-1, All}]]

Getting just one row, in this case the 5-th step:

CellularAutomaton[30, {{1}, 0}, 10, {{5}}]

Getting a range of rows:

Show[
        RasterGraphics[
          CellularAutomaton[30, {{1}, 0}, 15, {{5, 9}}]]];

Getting a single column - that is, a cell through time:

CellularAutomaton[30, {{1}, 0}, 15, {All, {0}}]

Flatten[CellularAutomaton[30, {{1}, 0}, 15, {All, {0}}]]

Getting a range of columns:

Show[
        RasterGraphics[
          CellularAutomaton[30, {{1}, 0}, 
            12, {All, {-3, 3}}]]];

Another possibility is to ask CellularAutomaton to only return cells that differ from the background:

Show[
        RasterGraphics[
          CellularAutomaton[110, {{1}, 0}, 30, {All, Automatic}], 
          Frame -> True, FrameTicks -> False]];

Coordinate system used:
For cyclic boundary conditions the coordinates start at zero on the leftmost cell.
For infinite boundary conditions the leftmost cell of the main input pattern is considered to be at coordinate zero.

Two dimensions and beyond

For two-dimensional systems, the resulting three-dimensional arrays have a lot of data, and are hard to understand in one go, so we can take "slices" through the systems space-time.

Getting the final step, which is a matrix:

Show[
        RasterGraphics[
          Last@CellularAutomaton[{49, {2, {{0, 2, 0}, {2, 1, 2}, {0, 2, 
                      0}}}, {1, 1}}, {{{1}}, {{0}}}, 
              30, {-1, All, All}]]];

Getting a single row through time -- a slice through the system.

Show[
        RasterGraphics[
          Flatten /@ 
            CellularAutomaton[{49, {2, {{0, 2, 0}, {2, 1, 2}, {0, 2, 
                      0}}}, {1, 1}}, {{{1}}, {{0}}}, 
              30, {All, {0}, All}]]];

CellularAutomaton can do any number of dimensions!

Using CellularAutomaton as part of another program

For an example see the CA-JLink download, which animates 2-D CAs.

Further information

The Mathematica book print edition.
Also the online version [link].

The Help Browser in Mathematica.

The end notes in A New Kind of Science, page 867 [online].

Ask a question on the Forum [link], or on MathGroup [link].

Ask one of the science group here.

Computer experiments clinic here later today.