Cellular Automata is simple

Imagine a field divided into square cells. In each cell, there is a person who can only see their 8 neighbors. This person can raise or lower a flag based on the beat of a metronome. They make their decision solely based on the number of flags raised by their neighbors.

Now, instead of raising flags, the little people will turn the light on or off for the cell they are standing on. And the people themselves can essentially be replaced by a sensor that checks "what's going on with the neighbors."

If we simplify it even further (since real cells and sensors are expensive) and leave an abstract grid of cells, where each cell changes its state based on the states of its neighbors, then what remains is an array of values plus a rule for changing them.

This is a cellular automaton — a mathematical model consisting of a grid of cells. Each cell can have one of several states (for example, “on” or “off”), and the state of each cell changes over time based on the states of its neighbors according to specific rules.

Why “cellular” is clear — because we have a grid. But what is an automaton? An automaton (finite) is a mathematical model that has input, output, and state (one of several possible). It can change its state depending on the input value and its current state. In our context, each cell in the grid is an individual automaton that interacts with its neighbors, updating its state according to predefined rules.

The simplest (and most famous) example is the “Game of Life.” This model was invented by John Conway in 1970 and has many modifications and extensions, but we will focus on the simplest version—the original one.

For clarity, we will use the Tiamat app (it's only available for iOS, but it's free and allows you to easily edit rules).

Conway's Game of Life

So, let’s start by defining the rules and neighbors. Each cell has 8 neighbors.

At each step, a cell turns on or off according to the following rules:

If a cell has 2 active neighbors, it retains its current state.
If a cell has 3 active neighbors, it becomes active.
In all other cases, it becomes inactive.

Original state

Step 0-1

A has 0 neighbors and becomes inactive on this step.
B has only 1 neighbor and becomes inactive on this step.
C has 3 neighbors and remains active (does not change its state).

Step 1-2

A has 0 neighbors, and it remains inactive.
B now has 3 neighbors and becomes active.
C has 2 neighbors and retains its previous state.

Step 2-3

A has 0 neighbors and remains inactive.
B has only 1 neighbor and becomes inactive again.
C has only 1 neighbor and also becomes inactive.

Step 3-4

A remains inactive.
B has 3 neighbors and becomes active again.
C now has 3 neighbors and also becomes active.

What’s remarkable about this simple model is that it allows for the simulation of quite complex and stable structures (sorry, the galaxy on the picturs is actually pulsar):

It’s best to try it yourself in a simulation app. There are plenty available online for various platforms. The most convenient for iOS is Tiamat, but if that’s not an option, there’s the cross-platform Golly.

Variations

What if we increase the number of neighbors? This leads to a class of cellular automata called Larger than Life (yes, there’s even a PhD dissertation on this topic). You can try it out in the same Tiamat app.

And if we make the number of possible cell states not discrete (0 or 1), but any value, we get Smooth Life, which later evolved further into Lenia:

Interesting Facts

The Game of Life is Turing complete, meaning it can perform any computation, including simulating itself.
There are theories that represent our universe and its physics at a fundamental level as a cellular automaton.
In fact, the dimensionality, cell shape, and state description can be almost anything. We've considered a simple two-dimensional, square-grid variant with two states for ease of understanding.
Cellular automata can also be found in nature, such as on the shells of certain mollusks.
Cellular automata are used in various sciences and disciplines to model processes.

George Ostrobrod, 2024