You are here

Patterns in Pascal's Triangle - with a Twist - Two-Dimensional Cellular Automata

Kathleen M. Shannon and Michael J. Bardzell

A two-dimensional cellular automaton consists of a grid of cells rather than a row of cells. As in the one-dimensional case, the cells have values from a finite alphabet and a local rule to update those values. In the one-dimensional case, the local neighborhood that determines the cell's next value consists of the cell itself and its neighbors to the left and to the right. Two-dimensional automata have neighbors in more directions.

The best known example of a two-dimensional cellular automaton is John Conway's Game of Life. (A web search on "Game of Life" will turn up numerous references, including programs you can download to experiment with the automaton. We list one such site in our References.)

We show two popular ways to specify a cell's neighborhood in the following figures. On the left, the neighborhood consists of nine cells, and on the right the neighborhood consists of only five. In a nine-point rule, all the cells in this three-by-three grid would be considered neighbors of the center cell. In a five-point rule, only those that share an edge with the center cell would be included. Thus the four corners, although diagonally adjacent to the center cell, are not available to the rule.

The same kinds of questions arise for two-dimensional cellular automata as for one-dimensional automata. As in the one-dimensional case, if we use a finite grid, there are only finitely many possible states, one of which is the state in which all cells have the value of zero (or the identity). If this state is reached, the cellular automaton continues in this state forever. Since there is really no action at this point, we generally refer to this state as "death" -- we say a cellular automaton initial state that eventually reaches this state "dies" or "dies out."

The red line is where the top and bottom join; the blue is where left and right join.As we did in our example in the one-dimensional case, we define the cells at the right hand edge of the grid and the cells at the left hand edge to be next-door neighbors. We also define the downstairs neighbors of the bottom row to be the first row and the upstairs neighbors of the first row to be the last row. In this manner we are really wrapping our rectangle into the surface of a donut shape or a torus.

Click here for some examples of group multiplication rule cellular automata. These were created by using a five-point rule of clockwise group multiplication, not including the center. The file contains some large animations and may take a while to load. If you are having trouble loading or running these animations, you might want to try our supercompressed versions instead.

We also include some examples of nine-point rule automata. This file also has large animations and may take a while to load. If you are having trouble loading or running these animations, you might want to try our supercompressed versions instead.

Andy's Applet's: Would you like to run your own two-dimensional automata? [[This link is no longer functional. Ed: 2013.]

There are a myriad of other questions one could ask, either spawned by the investigations outlined above or by going in other directions entirely. We have had students with interests in computer science, statistics, pure mathematics, and applied mathematics work with us on various questions that have spun off of these investigations. A full listing of even the extensions we have begun investigating is beyond the scope of this paper, but we refer you to the References for more information. We also invite you to think of your own questions. It seems that every investigation in mathematics leads to more new questions. Thus mathematics is an ever-growing rich field of knowledge. We hope you have enjoyed this small journey into just one of the many accessible niches in mathematics.

Kathleen M. Shannon and Michael J. Bardzell, "Patterns in Pascal's Triangle - with a Twist - Two-Dimensional Cellular Automata," Convergence (December 2004)