The Fascinating World of Cellular Automata and Their Applications

The Famous Rule 30 (Generated with Wolfram Alpha)

Stephen Wolfram, the mind behind WolframAlpha and the programming language Mathematica, poses significant inquiries into mathematics and computation. He has contributed extensively through scientific papers, books, and essays. In 2002, he released A New Kind of Science, a book that delves into simple computational systems. It presents various straightforward algorithms from a mathematical viewpoint and draws comparisons with tangible scientific occurrences. Wolfram asserts that one day, all physical systems will be representable through simple computing models, which he believes will redefine scientific standards.

The book stirred considerable debate due to its sweeping claims about science and its lack of citations. Wolfram often overlooked the contributions of other researchers upon which he relied, and his analytical methods have been critiqued for lacking rigor. Two decades later, he stands firm against these criticisms. Regardless of the controversies, A New Kind of Science remains a compelling read, albeit with a critical eye. The discourse around simple computational systems has gained momentum in the scientific community as a result. This article will explore a key aspect of Wolfram’s work: cellular automata and their diverse applications.

Cellular Automata

The highlight of A New Kind of Science is the exploration of simple cellular automata and the wide array of structures they can generate. To describe these objects in a one-dimensional context, we establish a "rule" identified by a numerical label. Below is the definition of Rule 30.

To create each subsequent row, we reference the row above. Each cell evaluates its own state alongside the cells directly above it and its adjacent cells. By applying this rule, we can determine whether the new cell will be black (1) or white (0). This rule can also be represented in binary as 00011110, where the decimal equivalent is 30, hence the rule's name. This framework allows for 256 potential rules.

Rule 30 starting from a single black cell (Source)

Try utilizing the Rule 30 definition to trace how the image was generated, beginning from the top row downwards. You’re not limited to starting with a single central black cell as shown, but this initial condition provides a standard format for visualizing these rules.

I selected Rule 30 as an example due to its intriguing behavior. However, many of the 256 rules within this category yield rather mundane results.

Rule 236 starting from a single black cell (Source)

Numerous rules simply generate a single black line, while others may not produce anything at all, becoming completely blank after the initial black cell. Introducing random starting conditions of black and white cells can yield more engaging results. The example below illustrates how Rule 236 becomes visually more compelling under these conditions, resembling a barcode.

Rule 236 starting from random initial conditions (Source)

Given the multitude of rules and patterns, a classification system to organize them is advantageous. Wolfram offers one in his book, and many have attempted to refine it. I will reference the classification from A New Kind of Science, which categorizes rules based on their behavior with random starting conditions.

Class 1: Convergence to Uniform

Class 1 rules are straightforward but predictable. Regardless of initial conditions, they will always converge to a uniform state. While they may begin with some structure, their long-term behavior is entirely predictable, resulting in a uniform outcome. Examples include Rule 0, Rule 160, and Rule 255.

Rule 0 (left), Rule 160 (center), and Rule 255 (right) which are all Class 1 rules (Source)

Class 2: Convergence to Stability

Class 2 rules offer a bit more excitement. Instead of leading to a wholly black or white state, they stabilize into predictable periodic patterns. Often, Class 2 results appear like a barcode or a variation thereof, distinguishing them from Class 1 rules, which lack such diversity. Rule 108 exemplifies a Class 2 rule, as does the previously mentioned Rule 236.

Rule 108, a slightly more interesting Class 2 rule (Source)

Class 2 rules can display captivating behaviors based on initial conditions. For instance, Rule 218, under random starting conditions, produces a typical barcode shape. However, with a single black cell at the start, it generates the renowned Sierpi?ski triangle. This illustrates the remarkable potential of cellular automata to create complex structures from basic rules.

Rule 218, a Class 2 rule that has fascinating behavior under the right initial conditions (Source)

Importantly, this exceptional case of Rule 218 adheres to the Class 2 definition. While visually striking, the Sierpi?ski triangle remains predictable and periodic, fitting within this classification.

Class 3: Random Patterns

Class 3 rules yield structures that may exhibit patterns, yet they often appear random. They are commonly labeled as random, though this is misleading since they arise from well-defined rules (albeit with random initial patterns). This is where cellular automata become particularly fascinating, with many Class 3 rules functioning as pseudo-random number generators. Rule 30, mentioned earlier, is a Class 3 example, and further illustrations follow.

Rule 22, a Class 3 rule, with random initial conditions (Source)

Rule 150, another Class 3 rule, with random initial conditions (Source)

Rule 30 is especially intriguing due to its resemblance to patterns found in nature. The shell of the Conus textile snail showcases a pattern strikingly similar to Rule 30. Is this an instance of cellular automata in nature, or merely a reflection of our inclination to connect mathematics with the natural world?

Class 4: Order and Chaos

Class 4 rules transcend the boundaries typically associated with such simple systems. They combine repetitive structures like those in Class 2 with random elements found in Class 3. One notable example, Rule 110, has been shown to possess universal computation capabilities.

At first glance, Rule 110 might appear similar to Class 3 rules. However, its uniqueness lies in the movement of diverse patterns down the image, with various triangles appearing to travel left and right. This motion allows information to be stored within a Class 4 rule. When these patterns interact, new formations emerge and move in distinct directions.

Altering the initial conditions can lead to widely varying outcomes. Since Rule 110 is Turing complete, it theoretically can perform any calculation!

All of this becomes even more impressive when considering that the cellular automata discussed in this article represent only the most fundamental forms. We can also explore rules involving larger groups of cells, multi-color systems, and even higher dimensions! The "elementary cellular automata" we've covered are just the beginning.

Conway’s Game of Life

One of the most recognized examples of cellular automata is Conway’s Game of Life. Developed by John Conway in the 1960s, this system is defined by a simple two-dimensional rule. Each cell updates based on its immediate neighbors and diagonals, with only two possible states for each cell.

This framework can sustain numerous stable, oscillating, and moving entities, some of which have quirky names like “Loaf,” “Toad,” “Pulsar,” and “Heavy-weight spaceship.” Conway’s Game of Life is also Turing complete, enabling it to simulate any Turing machine. Like Rule 110, it can achieve this due to its ability to create persistent and interactive structures.

Conway’s Game of Life represents just one of many potential rules for a two-dimensional system. Similar to the simple automata discussed earlier, countless variations of these systems have been discovered.

The vast potential in the study of cellular automata is evident. This article merely scratches the surface of a rich field of investigation. Researchers from various disciplines are exploring the capabilities of these systems to model natural phenomena.

If you’re eager to learn more about cellular automata, you’re in luck! There’s an abundance of information available online, complete with stunning visuals. Below are some resources to help you get started:

The book that initiated this exploration, A New Kind of Science, is a fascinating read for a comprehensive overview of cellular automata. I also recommend exploring critiques of the book for a balanced perspective.
For a comprehensive database of simple programs like the elementary cellular automata discussed here, visit The Wolfram Atlas.
To experiment with various elementary cellular automata rules and initial conditions, check out this user-friendly website.
If you’re curious about Rule 110 and its Turing completeness, the relevant Wikipedia page provides a solid overview.
This website allows you to interact with various 2D rules, including Conway's Game of Life and one dubbed “Live Free or Die.”
For a more philosophical take on cellular automata, refer to the Stanford Encyclopedia of Philosophy’s section on the topic.

I hope you gained valuable insights! If you appreciate my work, please consider becoming a Medium member through this link to support me! Feel free to follow me for more articles like this, as I publish weekly on math and science.