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.

Elementary automata are particularly interesting for two reasons:

- The limited number of rules and interactions make them very easy to study.
- 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.

Pattern (L,C,R) | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
---|---|---|---|---|---|---|---|---|

Next Generation | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |

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:

- Automata in which patterns generally stabilize into homogenity.
- Automata in which patterns evolve into mostly stable or oscillating structures.
- Automata in which patterns evolve in a seemingly chaotic fashion.
- 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.

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.

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

Time Step | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|

0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |

1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
1 |

2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
1 |
1 |

3 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
1 |
0 | 1 |

4 | 0 | 0 | 0 | 0 | 0 | 1 |
1 |
1 |
1 |
1 |

5 | 0 | 0 | 0 | 0 | 1 |
1 |
0 | 0 | 0 | 1 |

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.

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

```
■
■■
■■■
■■ ■
■■■■■
■■ ■
■■■ ■■
■■ ■ ■■■
■■■■■■■ ■
■■ ■■■
■■■ ■■ ■
■■ ■ ■■■■■
■■■■■ ■■ ■
■■ ■ ■■■ ■■
■■■ ■■■■ ■ ■■■
■■ ■ ■■ ■■■■■ ■
■■■■■■■■ ■■ ■■■
■■ ■■■■ ■■ ■
■■■ ■■ ■ ■■■■■
■■ ■ ■■■ ■■■■ ■
■■■■■ ■■ ■■■ ■ ■■
■■ ■ ■■■■■ ■ ■■ ■■■
■■■ ■■ ■■ ■■■■■■■■ ■
■■ ■ ■■■■■■ ■■ ■■■
■■■■■■■ ■ ■■■ ■■ ■
■■ ■ ■■■■ ■ ■■■■■
■■■ ■■ ■■ ■■■ ■■ ■
```

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.

```
■■■
■■ ■■
■■■■■■■
■■ ■■
■■■■ ■■■■
■■ ■■ ■■ ■■
■■■■■■■■■■■■■■■
■■ ■■
■■■■ ■■■■
■■ ■■ ■■ ■■
■■■■■■■■ ■■■■■■■■
■■ ■■ ■■ ■■
■■■■ ■■■■ ■■■■ ■■■■
■■ ■■ ■■ ■■ ■■ ■■ ■■ ■■
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
■■ ■■
■■■■ ■■■■
■■ ■■ ■■ ■■
■■■■■■■■ ■■■■■■■■
■■ ■■ ■■ ■■
■■■■ ■■■■ ■■■■ ■■■■
■■ ■■ ■■ ■■ ■■ ■■ ■■ ■■
■■■■■■■■■■■■■■■■ ■■■■■■■■■■■■■■■■
■■ ■■ ■■ ■■
■■■ ■■■■ ■■■■ ■■
■ ■■ ■■ ■■ ■■ ■■ ■■■
■■■■■ ■■■■■■■■ ■■■■■■■■ ■■■■
■ ■■ ■■ ■■ ■■ ■■ ■■ ■
■■ ■■■■ ■■■■ ■■■■ ■■■■ ■■■■ ■■ ■
```

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!