A Beginner's Guide To Cellular Automata

A Computer Workshop at the NKS2003 Conference on 27 June 2003

Prepared and Presented by Matthew Szudzik (mszudzik@wolfram.com)

Introduction to Mathematica

Although Mathematica is best known for its ability to do integrals, sum infinite series, and do   other essential calculations in traditional mathematics, Mathematica is also an excellent tool for studying cellular automata.  Before we   begin, please place your cursor in the cell below and press ⇧-  ⌤.  If the message "Cellular Automata Successfully Defined"   appears, then the definitions needed for this workshop have been successfully   loaded.  (Please note that your version of Mathematica must have the NKSExplorer package installed if you plan to use the   commands CASteps or CARule that are defined in this document.)

CAGraphics[data_, 
          opts___] := (Show[
              Graphics[Raster[1 - Reverse[data]], opts, 
                AspectRatio -> 
                  Automatic]];);
CA[num_, init_, t_, opts___] := 
        CAGraphics[CellularAutomaton[num, init, t, {All, All}], 
          opts];
ParenInput[
          string_]  :=  
Flatten[If[
                First[#] === "(",  Table[0, {Length[#] + 1}], 
                Table[1, {Length[#] + 1}]] & /@ 
            Split[Characters[string]]];
<< NKSExplorer`;
CASteps[num_, t_, 
          opts___] :=  (Show[NKSGraphics[24.2, {num, t}], 
              opts];);
CARule[n_, 
          opts___] := (Show[NKSGraphics[24.1, {n}], 
              opts];);
StylePrint["Cellular Automata Successfully Defined!", 
        FontSize -> 18, FontWeight -> "Bold", 
        FontColor -> RGBColor[1, 0, 0]];

Cellular Automaton Rules

Example of a cellular automaton rule.

CARule[30]

CASteps[30, 10]

The binary representation of the rule number gives the pattern of black and white cells for the rule.

IntegerDigits[30, 2, 8]

CARule[30]

IntegerDigits[184, 2, 8]

CARule[184]

So, there are 256 different cellular automaton rules, assuming the we only   have two colors (black and white), and cells only depend on their nearest   neighbors. These are called the elementary cellular automata.

Mathematica CA interface

For this workshop, I defined the Mathematica function CA to generate graphics of cellular automata.  For example:

CA[30, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
        0}, 10]

My definition relies on the built-in function CellularAutomaton.  CellularAutomaton produces the data (a matrix of 0's and 1's), and then the function CAGraphics makes the picture.  For example,

data = 
CellularAutomaton[
        30, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
          0}, 10]

CAGraphics[data]

Now, it is annoying that I need to type so many 0's and 1's to describe a   simple initial condition with only one black cell.   Let us look at the usage   message for the CellularAutomaton function in the Mathematica Help Browser…

According to the Help Browser, we can enter {{cells}, {background}} as the initial condition. So, for example:

CA[30, {{1, 1}, {0, 1}}, 10]

CA[184, {{1, 1}, {0, 1}}, 10]

CA Equivalences

Consider cellular automaton rule 188

CARule[188]

and cellular automaton rule 230.

CARule[230]

Will their behaviors always be mirror images of each other?

CA[188, {{1}, {0}}, 32]

CA[230, {{1}, {0}}, 32]

Yes, they will be mirror images of each other because their rules are mirror images of each other.

Are there other cellular automata that are "equivalent" to rule 188 under trivial transformations?

Yes, cellular automaton rule 194 may be obtained from rule 188 by exchanging black and white. (Note that this transformation reflects and inverts the 
rule-icon.)

CARule[188]

CARule[194]

CA[188, {{1}, {0}}, 32]

CA[194, {{1}, {0}}, 32]

If they are "equivalent", then why do they behave differently on a single black cell?

Because we should have used a single WHITE cell (they are equivalent under the transformation that exchanges black and white).

CA[194, {{0}, {1}}, 32]

Every elementary cellular automaton is equivalent to three others by the transformations that exchange right for left, black for white, and the transformation that exchanges both right for left and black for white.  Rule 152 corresponds to rule 188 when one exchanges right for left and black for white.

CARule[152]

CA[152, {{0}, {1}}, 32]

Matching Parentheses

What sorts of computations can be performed by cellular automata?

One example is that rule 184 can be used as a parentheses checker.

CARule[184]

Given an arbitrary string of left and right parentheses, like "(()) (() (() (())))", it is often difficult to tell whether the parentheses are matched.  In fact, it requires a fair amount of computational sophistication to   decide if an arbitrary string of parentheses is matched—for   example, there is no regular expression that recognizes these strings.

Mathematica automatically checks parentheses matching.  Just type some parentheses.    Mathematica highlights unmatched parentheses in purple.

() ())) (((() ())) (

Interestingly, rule 184 can be understood as a parentheses matcher.  The   function ParenInput[str], gives an initial condition for rule 184 that corresponds to the string   str of parentheses.  For example:

ParenInput["((()()))((((((())))))"]

CA[184, 
      ParenInput["((()()()()()))()()()()()((((()))()()(((())))))"], 
      20]

Left parentheses correspond to right-moving regions of white cells, and right parentheses correspond to left-moving regions of black cells.  If the parentheses match, then the white and black regions annihilate each other, leaving only a checkerboard pattern.  If the parentheses do not match, then the regions will not annihilate each other.

CA[184, ParenInput["((())()()()))()()()()(((((()))()()(((())))))"], 
      20]

Warning!  Often with cellular automata, we assume cyclic boundary conditions. This means that we treat the cellular automaton as if the leftmost and rightmost cells were neighbors.  In this case, if we compute the example for more steps, the "unmatched" parentheses annihilate each other.

CA[184, ParenInput["((())()()()))()()()()(((((()))()()(((())))))"], 
      30]

So, rule 184 is only a parentheses matcher when the boundary conditions are not cyclic.

Rule 30

CA[30, {{1}, 0}, 100]

First[
      Cases[Transpose[
          CellularAutomaton[30, {{1}, 0}, 100]], {1, ___}]]

Is this sequence "random"?

Rule 110

CA[110, {{1}, 0}, 300]

How many steps until this computation becomes repetitive?