Cellular Automata

Cellular automata provide a convenient way to represent many kinds of systems in which the values of cells in an array are updated in discrete steps according to a local rule.

Generating a cellular automaton evolution.

This starts with the list given, then evolves rule 30 for four steps:

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

This shows 100 steps of rule 30 evolution from random initial conditions:

ArrayPlot[CellularAutomaton[30,RandomInteger[1,250],100]]

Ways of specifying initial conditions for one-dimensional cellular automata.

If you give an explicit list of initial values, (RefLink[CellularAutomaton, paclet:ref/CellularAutomaton]) will take the elements in this list to correspond to all the cells in the system, arranged cyclically.

The right neighbor of the cell at the end is the cell at the beginning:

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

It is often convenient to set up initial conditions in which there is a small "seed" region, superimposed on a constant "background". By default, (RefLink[CellularAutomaton, paclet:ref/CellularAutomaton]) automatically fills in enough background to cover the size of the pattern that can be produced in the number of steps of evolution you specify.

This shows rule 30 evolving from an initial condition containing a single black cell:

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

This shows rule 30 evolving from an initial condition consisting of a {1,1} seed on a background of repeated {1,0,1,1} blocks:

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

Particularly in studying interactions between structures, you may sometimes want to specify initial conditions for cellular automata in which certain blocks are placed at particular offsets.

This sets up an initial condition with black cells at offsets ±40:

ArrayPlot[CellularAutomaton[30,{{{{1},{-40}},{{1},{40}}},0},100]]

Specifying rules for one-dimensional cellular automata.

In the simplest cases, a cellular automaton allows k possible values or "colors" for each cell, and has rules that involve up to r neighbors on each side. The digits of the "rule number" n then specify what the color of a new cell should be for each possible configuration of the neighborhood.

This evolves a single neighborhood for 1 step:

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

Here are the 8 possible neighborhoods for a k==2, r==1 cellular automaton:

Tuples[{1,0},3]

This shows the new color of the center cell for each of the 8 neighborhoods:

Map[CellularAutomaton[30,#,1][[2,2]]&,%]

For rule 30, this sequence corresponds to the base-2 digits of the number 30:

FromDigits[%,2]

This runs the general k==3, r==1 rule with rule number 921408:

ArrayPlot[CellularAutomaton[{921408,3,1},{{1},0},100]]

For a general cellular automaton rule, each digit of the rule number specifies what color a different possible neighborhood of 2r+1 cells should yield. To find out which digit corresponds to which neighborhood, one effectively treats the cells in a neighborhood as digits in a number. For an r==1 cellular automaton, the number is obtained from the list of elements neig in the neighborhood by neig.{k^2,k,1}.

It is sometimes convenient to consider totalistic cellular automata, in which the new value of a cell depends only on the total of the values in its neighborhood. One can specify totalistic cellular automata by rule numbers or "codes" in which each digit refers to neighborhoods with a given total value, obtained for example from neig.{1,1,1}.

In general, (RefLink[CellularAutomaton, paclet:ref/CellularAutomaton]) allows one to specify rules using any sequence of weights. Another choice sometimes convenient is {k,1,k}, which yields outer totalistic rules.

This runs the k==3, r==1 totalistic rule with code number 867:

ArrayPlot[CellularAutomaton[{867,{3,1},1},{{1},0},100]]

Rules with range r involve all cells with offsets -r through +r. Sometimes it is convenient to think about rules that involve only cells with specific offsets. You can do this by replacing a single r with a list of offsets.

Any k==2 cellular automaton rule can be thought of as corresponding to a Boolean function. In the simplest case, basic Boolean functions like (RefLink[And, paclet:ref/And]) or (RefLink[Nor, paclet:ref/Nor]) take two arguments. These are conveniently specified in a cellular automaton rule as being at offsets {{0},{1}}. Note that for compatibility with handling higher-dimensional cellular automata, offsets must always be given in lists, even for one-dimensional cellular automata.

This generates the truth table for 2-cell-neighborhood rule number 7, which turns out to be the Boolean function Nand:

Map[CellularAutomaton[{7,2,{{0},{1}}},#,1][[2,2]]&,{{1,1},{1,0},{0,1},{0,0}}]

Rule numbers provide a highly compact way to specify cellular automaton rules. But sometimes it is more convenient to specify rules by giving an explicit function that should be applied to each possible neighborhood.

This runs an additive cellular automaton whose rule adds all values in each neighborhood modulo 4:

ArrayPlot[CellularAutomaton[{Mod[Apply[Plus,#],4]&,{},1},{{1},0},100]]

The function is given the step number as a second argument:

ArrayPlot[CellularAutomaton[{Mod[Total[#]+#2,4]&,{},1},{{1},0},100]]

When you specify rules by functions, the values of cells need not be integers:

ArrayPlot[CellularAutomaton[{Mod[1/2 Apply[Plus,#],1]&,{},1},{{1},0},100]]

They can even be symbolic:

Simplify[CellularAutomaton[{Mod[Apply[Plus,#],2]&,{},1},{{a},0},2],a ∈ Integers]

Selecting which steps to keep.

This runs rule 30 for 5 steps, keeping only the last step:

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

This keeps the last 2 steps:

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

This gives one step:

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

The step specification (Subscript[spec, t]) works very much like taking elements from a list with (RefLink[Take, paclet:ref/Take]). One difference, though, is that the initial condition for the cellular automaton is considered to be step 0. Note that any step specification of the form {…} must be enclosed in an additional list.

Cellular automaton step specifications.

This evolves for 100 steps, but keeps only every other step:

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

Selecting steps and cells to keep.

Much as you can specify which steps to keep in a cellular automaton evolution, so also you can specify which cells to keep. If you give an initial condition such as {{(Subscript[a, 1]),(Subscript[a, 2]),…},blist}, then (Subscript[r, d]) is taken to have offset 0 for the purpose of specifying which cells to keep.

Cellular automaton cell specifications.

This keeps all steps, but drops cells at offsets more than 20 on the left:

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

This keeps just the center column of cells:

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

If you give an initial condition such as  {{(Subscript[a, 1]),(Subscript[a, 2]),…},blist}, then (RefLink[CellularAutomaton, paclet:ref/CellularAutomaton]) will always effectively do the cellular automaton as if there were an infinite number of cells. By using a (Subscript[spec, x]) such as {(Subscript[x, 1]),(Subscript[x, 2])} you can tell (RefLink[CellularAutomaton, paclet:ref/CellularAutomaton]) to include only cells at specific offsets (Subscript[x, 1]) through (Subscript[x, 2]) in its output. (RefLink[CellularAutomaton, paclet:ref/CellularAutomaton]) by default includes cells out just far enough that their values never simply stay the same as in the background blist.

In general, given a cellular automaton rule with range r, cells out to distance rt on each side could in principle be affected in the evolution of the system. With (Subscript[spec, x]) being (RefLink[All, paclet:ref/All]), all these cells are included; with the default setting of (RefLink[Automatic, paclet:ref/Automatic]), cells whose values effectively stay the same as in blist are trimmed off.

By default, only the parts that are not constant black are kept:

ArrayPlot[CellularAutomaton[225,{{1},0},100]]

Using (RefLink[All, paclet:ref/All]) for (Subscript[spec, x]) includes all cells that could be affected by a cellular automaton with this range:

ArrayPlot[CellularAutomaton[225,{{1},0},{100,All}]]

(RefLink[CellularAutomaton, paclet:ref/CellularAutomaton]) generalizes quite directly to any number of dimensions. Above two dimensions, however, totalistic and other special types of rules tend to be more useful, since the number of entries in the rule table for a general rule rapidly becomes astronomical.

Higher-dimensional rule specifications.

This is the rule specification for the two-dimensional 9-neighbor totalistic cellular automaton with code 797:

code797={797,{2,1},{1,1}};

This gives steps 0 and 1 in its evolution:

CellularAutomaton[code797,{{{1}},0},1]

This shows step 70 in the evolution:

ArrayPlot[First[CellularAutomaton[code797, {{{1}}, 0},
                                               {{70}}]]]

This shows all steps in a slice along the x axis:

ArrayPlot[Map[First,
    CellularAutomaton[code797, {{{1}}, 0},
                                      {70, {0}, All}]]]