why cellular automata fascinate me
2023-11-03
Cellular automata have been fascinating me for a while now. Time to talk about it.
Cellular automata come in all sorts of varieties, in one to any number of dimensions. But to get to the bottom of they do fascinate me it is enough to look at simple one-dimensional cellular automata.
the basics
A cellular automaton is a system which works on an endless grid. In the horizontal axis one end quite often wraps around to the other one, to form a ring. The vertical axis can in some forms also wrap around (forming a torus), or just continue infinitely, for examples as rows in an output.
The grid consists of cells (x/y coordinates).
Each cell can — in the simplest cellular automata, which I'm focussing on here — either be alive or dead, active or inactive, binary one or binary zero.
primer on neighbourhoods
Whether or not a cell is alive or dead depends on the combination of states of its neighbours. This dependency forms the rule of a cellular automaton.
For 1-dimensional cellular automata, the active world / grid consists of a single row. The neighbourhood which determines the state of a cell are in the previous state of the world: The row above it. Specifically, the neighbourhood of a cell in 1d automata usually consists of the cell directly above it and the two neighbours of that cell:
....LMR....
.....X.....
`X` here is the cell we're looking at, its neighbourhood is the cell directly above it `M`, and its two neighbours `L` and `R`.
The individual states of these three neighbourhood cells determine the state of the `X` cell.
Wolfram rules
Stephen Wolfram has formulated a very useful convention to declare what a specific rule for a 1d cellular automaton is:
You can consider the three neighbourhood cell states as three bits of information. For each combination of these three bits (8 possible combinations) we need to determine whether the target cell `X` is alive or dead, 1 or 0.
This realization makes way to a binary notation of 1s and 0s for all 8 combinations. And since eight bits make up one byte, we can conveniently communicate the rule for any given 1d cellular automaton as a number between 0 and 255.
somewhat well-known 1d automata rules
You may not it by name but most of you will have seen this shape:
1
1 1
1 1
1 1 1 1
1 1
1 1 1 1
1 1 1 1
1 1 1 1 1 1 1 1
1 1
1 1 1 1
1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1
1 1 1 1
1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
This is the Sierpinsky Triangle. It is a fractal, a self-similar shape. The Sierpinsky triangle can be generated by a 1-dimensional cellular automaton with rule 90. 90 in binary being `01011010`. Just this rule and a single active cell in the top row, will lead to an endlessly growing shape like the one above.
Let's decompose the binary representation of rule 90, `01011010`, to see how it generates that shape:
111 110 101 100 011 010 001 000 <-- 8 possible combinations of neighbour states
0 1 0 1 1 0 1 0 <-- resulting state of the cell
So you see, if only the `M` cell directly above `X` is alive, we have neighbourhood `010` and according to the table above, the `X` cell will die.
But the cell immediately to the left of `X` will have its `R` neighbour as the only alive one (`001`), and as per rule 90 it'll become alive. The same is true in a mirrored way for the cell immediately to the right of `X`: Its neighbourhood is `100`, which also means it'll become active under rule 90.
The cellular automaton calculates all states of all cells in a row based on the cells of the previous one, then repeat with the next row.
Another interesting rule is rule 110, or `01101110` in binary. It generates a somewhat random looking triangle shape. The curious thing about rule 110 is that it has been proven to be Turing complete in a truely infinite grid. That is to say, with the right initial cell configuration (you'd need _lots_ of predetermined cells) you can compute anything. In theory you can implement a whole computer operating system with rule 110. Not that it is practical: It'd be slow and enormous.
A third honorary mention must be rule 30. It also generates random shapes, but the randomness or 1s and 0s in every column is so good that it has been used as a pseudo random-number generator in computer programs.
about my fascination
Cellular automata exhibit emergent complexity out of very simple rules and preconditions. When you have a single active cell on a grid and a single byte of instructions how to build all future states, you wouldn't think this can possibly lead to anything even remotely complex or interesting.
And yet it does.
Emergent complexity is everywhere in our world, and cellular automata are a great simple way to shine a light and to simulate a small part of that.
I invite you to take some time with the search engine of your choice and tumble down the rabbit hole of cellular automata. It leads to truely crazy places. And it keeps reminding me that to produce something complex, evolving and seemingly “alive”, we don't need very much.
---