Cellular Automata

While recovering from wisdom tooth extraction in May, 2007, I decided to occupy myself by writing a computer program to draw cellular automata. For those unfamiliar with cellular automata, the idea is simple. To create a cellular automaton, start with a grid whose boxes are blank, and color in one box. Then, move down one row. Each box in that row is then either colored or not, depending on a rule that incorporates the three boxes right above it in the previous row. Continue coloring boxes in this manner. [For practical purposes, it is easy to make the first colored box in the top row, middle column. Also, since the grid will have finite width, I'll say more about boxes on the edges in a moment...]

A natural question is, how many "rules" are there for creating an automaton? First, let's consider an individual box, and the three boxes above it in the previous row. How many possible configurations are there for the three boxes? Still assuming that a box can either be colored or blank, there are 2^3 = 8 configurations. That is, two choices for the first box, times two choices for the second box, times two choices for the last box. Here are the eight configurations.

To determine a rule, we must look at each configuration and then decide to either color the corresponding lower box or leave it blank. This gives two choices per configuration, so there are 2^(2^3) = 2^8 = 256 rules. For example, the images above determine a (boring) rule, but here is another.

Here is the beginning of the automaton determined by this rule.

Addressing the above unresolved question, what happens if we want the image to be of arbitary height, while the width is constrained? My solution to this was to make the image "cylindrical" in the following sense: the left-most box in a row sees the box right above it, the box to the upper right, but since there no box to the upper left, it uses the last box in the previous row. Similarly, the last box in a row sees the first box in the previous row. This way, we can create an image as tall as we like, but with a fixed width. This was implemented using modular arithmetic. If the image has width w, then the boxes above the i-th box in a row are i-1 (mod w), i (mod w), and i+1 (mod w).

Aesthetically speaking, there is no good reason to only use black and white all the time, so I added a feature to change the colors used. Also, there is the question of the first row. Why should it be blank except for one box? I thought I could make things more interesting by adding an option to randomize the first row. I also added an option to increase the box size by a factor of 2. Here are a few examples --click to enlarge.

Another natural question to ask is, "What is so special about two colors?" The answer, of course, is "nothing." The next modification to the program was to consider 3 colors, and then arbitrarily many colors. As the number of colors increases, so does the complexity. This is apparent in the number of possible rules. For the three boxes above a given box, we now have 3^3 = 27 possible configurations. If for each such configuration we must select a color from three, then there are 3^(3^3) = 3^27 = 7,625,597,484,987 rules! That is roughly a thousand rules for each person on earth! I was able to create an interface for the 3-color version, with 27 buttons to set the rules. Here are some results.

I pasted together some series of images generated by the same rule.

To count the number of possible rules of an arbitrary number, say n, of colors, we follow the same counting procedure. There are n^3 configurations, and each has n choices associated to create a rule. This means there are n^(n^3) possible rules. This immediately ruled out a nice interface for selecting a rule by hand, so I opted to allow only random rule generation. At this point, even specifying a rule becomes unweidly. The most logical way to specify a rule is to use a base-n number with each digit representing a configuration (so there are n^3 digits needed to specify each rule). When there are 7 colors, 7^3 = 343, and this is more characters than most operating systems will allow in a filename. This makes it impractical to use this naming scheme to save an image with a name that containes the rule info used to generate that image.

One thing I noticed was that the "interestingness" of the images peaks at around 3 or 4 colors. When there are too many colors, things look too random, like colorful static. Here are some examples.

There are further generalizations that I didn't have time to explore. Why limit the effect of the previous row to just three boxes that are directly above the given box. The coloring of a box could depend on any number of boxes from any number of previous rows. This could make things much, much more complex. Also, why limit the progression of an automaton to just one direction (namely, "down")? I imagine one could start with a box and progress radially outward away from it. Why should the automaton be 2-dimensional? There is a natural extension to 3-dimensions, where the color of a box depends on the 9 boxes (or others!) in a slice above it. (This, however, seems like it would not have the same beauty, since one could only see the exterior boxes.) An automaton could also be animated in a number of ways. Someday perhaps I'll get around to looking at these more closely.