Category Archives: Cellular Automatica

Reversible Cellular Automata

One-dimensional cellular automata are closely associated with dynamical systems and modern chaos theory. While the results are complex and intriguing, the basic principle of cellular automata is simple:  Given an infinite row of cells with each cell colored either black (on or 1) or white (off or 0).  With each iteration, the cells are recolored based upon the colors of their neighbors.

A simple example of a transition rule is the following:  If the sum of  values of the two adjacent squares is even (equal to 0 (mod 2)), color the cell white in the next iteration, otherwise color it black. Under this rule, the initial row becomes:

graph1

 The simplest way to see the effects of a transition rule is to show the evolution of the row over time.  Thus, each row represents one iteration of the transition rule.  Below we see the first 4 iterations of the transition rule described above.

graph2

Which translates into the following diagram using white and black instead of 0’s and 1’s.

graph3

When describing the cellular automata with a sequence of successive rows, it is helpful to describe the transition rule locally.  The new value of a cell in the \(n^{th}\) row is determined by the values lying directly above it in the \((n-1)^{th}\) row.  Thus:

\(frac{111}{0}  frac{110}{1}  frac{101}{0}  frac{100}{1}  frac{011}{1} frac{010}{0}  frac{001}{1}  frac{000}{0} \)

describes the transition rule given above.  The upper part shows one of the eight possible states that three adjacent cells can have at iteration \(n\), where the lower part shows the state of the central cell of the trio time \(n+1\).  Since \(01011010 = 90\) in base two, the rule above is called the rule of 90.

For which Rules and which size neighborhoods is the cellular automata reversible (that is, you can determine the \((n-1)^{th}\) row from the \(n^{th}\) row?  Does each Rule have an inverse Rule?  Can Rules be composed and if so, does order matter?  Suppose the next state depends on the previous two states, does this create any new structures?