Understanding Cellular Automata

Usually represented in the form of a grid with flickering lights, cellular automata evolve over time using habitually very simple rules. Yet, they can somehow produce extremely complex behaviors...

A cellular automaton is a mathematical system that can be represented in the form of a table. The cells in the table typically only have two possible state : on or off corresponding to : alive or dead.

Un planeur issu du célèbre jeu de la vie de John Conway. Example table : alive cells are white, dead cells are grey.

Calculating if a cell is dead or alive :
To know if a cell is dead or alive we'll first need to define it's neighborhood.

What's a neighborhood ?

It corresponds to the cells that we consider are neighbors to our cell. In a cellular automaton, the state of a cell will depend on the state of its neighbors. So, to calculate the state of our cell, we first need to define who are its neighbors. Usually, we'll pick relative positions corresponding to adjacent cells.

Exemples differents de voisinage. Different possible neighborhood examples : neighboors of the white cell are colored in blue.

For every step of our simulation, each cell will simultaneously calculate it's next state depending on if it's neighbors are dead or alive.

In simpler cellular automata, each cell will simply add up its neirboring alive cells and depending on a set threshhold will become alive or stay dead.

In Conway's Game of Life, the most famous cellular automaton :


More complex automata can have more complicated rules.

Exemples differents de voisinage. Glider structure found in the Game of Life, this structure is able to move forever in a direction.

Despite their simple rules, cellular automata can produce extremely complex behaviors, that can result in chaotic or organised structures.

Exemples differents de voisinage. Elementary cellular automata

Some might see in cellular automata an allegory of our own universe. The arguably simple and universal laws of physics allow objects (cells) to interact and produce complexe results. They are also incredibly fun to interact with and watch.