NKS Research Tools

An introduction to the CellularAutomaton function.

Richard Phillips

Wolfram Research, Inc.

• What is CellularAutomaton?

• What is CellularAutomaton?

• It is a single function in Wolfram Mathematica for computing evolutions of cellular automaton rules.

It is simple to use in simple cases.

It is also general purpose, and can work out any possible case. (A universal tool.)

Occasionally, more complicated uses may require multiple calls to the function.

It is pretty fast, and uses internal optimizations.

• What is a simple example of what CellularAutomaton can do?

• What is a simple example of what CellularAutomaton can do?

• Here is one:

ArrayPlot[CellularAutomaton[30, {{1}, 0}, 20]]

• So it generates the values of the cells in a single run of a single cellular automaton rule?

• So it generates the values of the cells in a run of a single cellular automaton rule?

• Yes.  Here is rule 30 again for three steps, and without plotting:

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

• Cell values are usually represented using integers.

• Cell values are usually represented using integers.

• For two colors, use 0 for white, and 1 for black.

({{0  , =,   }, {1  , =,   }})

• Cell values are usually represented using integers.

• For two colors, use 0 for white, and 1 for black.

• For k colors, use 0 for white and k-1 for black, and shades of gray for the other values.

({{, , , , }, {0, 1, 2, 3, 4}})

It is possible to use other conventions but probably not often necessary.

But when using Function to specify a rule, the cells can be arbitrary expressions in general.

• Rows of cells are just lists of individual cell values.

({{{0, 1, 0, 1, 1}  , =,   }})

• Two dimensional arrays are just matrices of cell values.

({{{{0, 1, 0, 1}, {0, 0, 0, 1}}  , =,  }})

• And so on ... for any number of dimensions.

• Multiple steps of a rule's evolution are represented as a list of the states at each step.

So a one-dimensional rule produces a list of rows (a matrix) as output.

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

Writing this more clearly, with the step number.

• Basic examples: Rule 30 elementary cellular automata.

Here is rule 30 run for 3 steps, from a single one on an infinite background of zeros.

ArrayPlot[CellularAutomaton[30, {{1}, 0}, 3], Mesh -> True]

• Basic example: Rule 110 elementary cellular automata.

Here is rule 110 run for 29 steps, from a single one on an infinite background of zeros.

ArrayPlot[CellularAutomaton[110, {{1}, 0}, 29]]

Specifying the inputs.

CellularAutomaton is called with either three or four 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,whichCellsToReturn]

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

• First argument: the rule.

• First argument: the rule.

• Elementary cellular automaton.

Just use an integer between 0 and 255.

CellularAutomaton[integer,… ]

ArrayPlot[CellularAutomaton[90, {{1}, 0}, 30]]

• First argument: the rule.

• Any number of colors, nearest neighbors.

Using more colors, but still considering the nearest neighbors.

CellularAutomaton[{integer,colors},… ]

Here is a three color nearest neighbor rule

ArrayPlot[
      CellularAutomaton[{2067496389638, 3}, {{1}, 0}, 30]]

• First argument: the rule.

• Any number of colors, any number of neighbors on either side.

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

For example, the following form of neighborhood:

is achieved by using:

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

ArrayPlot[
      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

• First argument: the rule.

• Controlling the meaning of the rule number more explicitely.

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

What I have called the "weights" here, is just a list of non-negative integers.

A range one example will illustrate 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.

The form of arguments omitting the weights is in fact just a shorthand for assuming these particular weights.

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

• First argument: the rule.

• Totalistic rules.

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 one totalistic rules are written:

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

A useful allowed shorthand is:

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

• First argument: the rule.

• Outer-totalistic rules.

The range one outer-totalistic rules are:

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

• First argument: the rule.

• Ignoring certain neighbors.

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 zero for the corresponding weight value.

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},… ]

ArrayPlot[
      CellularAutomaton[{6, {2, {2, 1, 0}}, 1}, {{1}, 0}, 30]]

• Second argument: the initial cells.

There are two forms for this argument.

• Second argument: the initial cells.

• Cyclic array of cells.

CellularAutomaton[rule,list,…]

ArrayPlot[CellularAutomaton[2, {0, 0, 0, 1, 0, 0}, 8]]

• Second argument: the initial cells.

• Unbounded array of cells.

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

The background is uniformly white is this example:

ArrayPlot[CellularAutomaton[2, {{1}, 0}, 8]]

• Second argument: the initial cells.

• Unbounded array of cells, with cyclical background pattern.

ArrayPlot[CellularAutomaton[30, {{1, 1}, {1, 0, 1, 1}}, 50]]

• Second argument: the initial cells.

• Placing sub-arrays of cells at specific positions in an unbounded array.

ArrayPlot[
      CellularAutomaton[30, {{{{1}, {-10}}, {{1, 1}, {20}}}, 0}, 
        50]]

• Third argument: the number of steps.

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

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

• Fourth argument: which cells to return.

The optional forth argument is used to output only certain rows and columns of the evolution array.

• Fourth argument: which cells to return.

• Returning the last step.

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

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

• Fourth argument: which cells to return.

• Returning only certain steps.

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

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

Getting a range of steps:

ArrayPlot[CellularAutomaton[30, {{1}, 0}, 15, {{5, 9}}]]

• Fourth argument: which cells to return.

• Returning only certain spatial positions.

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:

ArrayPlot[
      CellularAutomaton[30, {{1}, 0}, 12, {All, {-3, 3}}]]

• Fourth argument: which cells to return.

• Returning only cells that differ from the evolving background pattern.

ArrayPlot[
      CellularAutomaton[110, {{1}, 0}, 30, {All, Automatic}]]

A further point: the co-ordinate system used:
• For cyclic boundary conditions the spatial 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 spatial coordinate zero.

• Two-dimensional cellular automata.

For two-dimensional systems, the resulting three-dimensional output arrays have a lot of data, and are hard to understand in one go.

One solution is to take two-dimensional "slices" through the three-dimensional output in space and/or time. CellularAutomaton supports this.

Such a slice can then be plotted using ArrayPlot.

• Two dimensional cellular automata.

• Returning only the final step.

ArrayPlot[
      Last@CellularAutomaton[{49, {2, {{0, 2, 0}, {2, 1, 2}, {0, 2, 0}}}, {1, 
              1}}, {{{1}}, {{0}}}, 30, {-1, All, All}]]

• Two dimensional cellular automata.

• Returning all steps of a single row.

ArrayPlot[
      Flatten /@ CellularAutomaton[{49, {2, {{0, 2, 0}, {2, 1, 2}, {0, 2, 
                  0}}}, {1, 1}}, {{{1}}, {{0}}}, 
          30, {All, {0}, All}]]

Three- and higher spatial dimension systems work too, by the way.

• Further information.

The Mathematica book print edition.

The Mathematica book 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.

NKS Computer experiments clinic at 8pm Saturday.