Sometimes the best way to learn about something is to create it. If I want to learn about an interesting subset of mathematics, eigenvalues perhaps, the explanation of the math can only go so far. I must let my pencil do the talking as I learn through construction. Programming is no different. So, when I became interested in cellular automata, I decided to make some examples of different types. Today, we can go over elementary automata.

Figure 1: An example of elementary cellular automata following rule 110. Each row in the image represents a segment of time in a time series from top to bottom. Each back space represent an organism, and each white space represents a dead organism. By defining a rule set, we can determine the outcome of the system. Rule 110 is named as the binary equivalent to the binary series 01101110.

Elementary automata are particularly interesting for two reasons:

1. The limited number of rules and interactions make them very easy to study.
2. The visual nature of time allows for deep investigation into changing patterns.

With these two characteristics, elementary cellular automata have become a tool to explore emergence, chaos, and complexity in a non-linear system.

The mechanism of elementary life is simple. Evaluate a cell’s neighbors, and depending on the rule set create a corresponding cell in the next generation. Since elementary cellular automatons are one dimensional, the algorithm must only evaluate the neighbors to their left or right. Their future state is then dependent on the rule set. One such rule set is rule 110, as seen in Table 1.

Table 1: Generational rule set that describes future generations following Rule 110.

As noted in Table 1, there are 8 patterns of 3 bits which determine the next generation of life. The 8 bit next generation is the source of the rule’s name, rule 110 is the rule whose next generation follows a 01101110 pattern, or the integer 110 in binary. Due to the flexibility provided in the rules, there are 4 classes of elementary behavior:

1. Automata in which patterns generally stabilize into homogenity.
2. Automata in which patterns evolve into mostly stable or oscillating structures.
3. Automata in which patterns evolve in a seemingly chaotic fashion.
4. Automata in which patterns become extremely complex and may last for a long time, with stable local structures.

Class 1 cellular automata would include things like rules 0, 8, 4, 10, and 12. One such example is rule 36, which results in vertical lines. In this case the rule set only 101 and 010 result in a new generation of life. Class 2 cellular automata includes rule 19, 26, 27, and 35. This can be seen in Figure 2 with rule 26. In the case of rule 26, the rule set allows for oscillation of the cells through time.

Figure 2: An example of oscillating elementary cellular automata following rule 26. Due to the rule set provided, the life generated oscillated between triangles of different sizes. In this case the figure is mathematically interesting because it's self-similarity in triangular structure makes it visually similar to the [Sierpinski Triangle][Sierpinski].

Class 3 automatons are particularly chaotic and include rules 22, 30, 126, 150, and 182. This class of automata are intriguing in that they provide chaotic results – deterministic results that heavily depend on initial conditions. As seen in Figure 3, chaotic automatons result in a wide variety of patterns and in many ways provide an interesting example of deterministic chaos.

Figure 3: An example of chaotic elementary cellular automata following rule 30. Due to the rule set provided, the life generated creates a chaotic pattern of geometric shapes. This provides a classic case of chaos in mathematics, in which a deterministic system is able to evolve into an unpredictable state due to heavily depending on initial conditions.

The process of generating a cellular automaton is generally simple. All that is required is to populate a one-dimensional with an initial population of 1s, test each grouping of three for the next generation’s population ad infinitum. An example following Rule 110 would be

This isn’t something particularly fun to do by hand, so let’s use a computer! Using python for some quick prototyping, we can simulate an elementary automaton.

# -_- coding: utf-8 -_-

# Assign a width to the world, and a maximum time.

width, maxTime = 30, 30

# Generate the matrix to operate on.

Matrix = [["0" for x in range(width)] for x in range(maxTime)]

# Set the current time

time = 0

# Set the rules, by listing the patterns that result in a new

# generation.

rules = ["110","101","011","010","001"]

# Populate the intial population

Matrix[time][width-1] = "1"

# Iterate the system over time

for time in range(1,maxTime):

    # Look at each pattern
    for index in range(1, width-1):
        # Check if the pattern is in the rule set
        if ''.join([Matrix[time-1][index-1],
                    Matrix[time-1][index],
                    Matrix[time-1][index+1]]) in rules:
            Matrix[time][index] = "1"
    string = ''.join(Matrix[time])
    print string.replace('1','■').replace('0',' ')

With these 12 lines of code, we get a rudimentary example of cellular automata as a series of lines of text life Figure 4.

                          ■
                         ■■
                        ■■■
                       ■■ ■
                      ■■■■■
                     ■■   ■
                    ■■■  ■■
                   ■■ ■ ■■■
                  ■■■■■■■ ■
                 ■■     ■■■
                ■■■    ■■ ■
               ■■ ■   ■■■■■
              ■■■■■  ■■   ■
             ■■   ■ ■■■  ■■
            ■■■  ■■■■ ■ ■■■
           ■■ ■ ■■  ■■■■■ ■
          ■■■■■■■■ ■■   ■■■
         ■■      ■■■■  ■■ ■
        ■■■     ■■  ■ ■■■■■
       ■■ ■    ■■■ ■■■■   ■
      ■■■■■   ■■ ■■■  ■  ■■
     ■■   ■  ■■■■■ ■ ■■ ■■■
    ■■■  ■■ ■■   ■■■■■■■■ ■
   ■■ ■ ■■■■■■  ■■      ■■■
  ■■■■■■■    ■ ■■■     ■■ ■
 ■■     ■   ■■■■ ■    ■■■■■
■■■    ■■  ■■  ■■■   ■■   ■

Figure 4: A sample of rule 110 in a text-based cellular automaton simulation. The light squares represent cells with life. The discrete nature of the automaton allows for representation in any discrete form, such as text.

In our basic script to generate cellular automatons, we only need to adjust the rule set to achieve the full set of cellular automatons. For example, we can set rules = ["101","100","011","010"] and we instead get a Sierpinski-esque rule 60 as seen in Figure 5.

                        ■■■
                       ■■ ■■
                      ■■■■■■■
                     ■■     ■■
                    ■■■■   ■■■■
                   ■■  ■■ ■■  ■■
                  ■■■■■■■■■■■■■■■
                 ■■             ■■
                ■■■■           ■■■■
               ■■  ■■         ■■  ■■
              ■■■■■■■■       ■■■■■■■■
             ■■      ■■     ■■      ■■
            ■■■■    ■■■■   ■■■■    ■■■■
           ■■  ■■  ■■  ■■ ■■  ■■  ■■  ■■
          ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
         ■■                              ■■
        ■■■■                            ■■■■
       ■■  ■■                          ■■   ■■
      ■■■■■■■■                       ■■■■■■■■
     ■■      ■■                      ■■      ■■
    ■■■■    ■■■■                   ■■■■    ■■■■
   ■■  ■■  ■■  ■■                 ■■  ■■  ■■  ■■
  ■■■■■■■■■■■■■■■■             ■■■■■■■■■■■■■■■■
 ■■              ■■             ■■                ■■
 ■■■            ■■■■           ■■■■              ■■
 ■ ■■          ■■  ■■         ■■  ■■            ■■■
 ■■■■■        ■■■■■■■■      ■■■■■■■■         ■■■■
 ■   ■■      ■■      ■■      ■■      ■■       ■■  ■
 ■■ ■■■■    ■■■■    ■■■■   ■■■■    ■■■■    ■■   ■

Figure 5: A sample of rule 126 in a text-based cellular automaton simulation. The rough spatial qualities of the cellular automaton allows for only an approximation to a Sierpinski triangle.

The possibilities for elementary cellular automata are limited to only 256 rules, but it presented an opportunity at their initial creation to learn a new kind of science. A science in which initial conditions present a highly deterministic yet unpredictable output. This boundary between order, complexity, and chaos presented a generation of mathematicians and computer scientists with a new way to explore life in a newfound digital space. With each new cell pattern came a new thought about the future of digital life and a glimpse at the limits of theoretical computing.

A more advanced elementary cellular automaton simulator using Numpy and PyGame can be found in my cellular automata github repository. Enjoy your cellular automaton explorations!