I've been wanting to write about the way I generated the background image for this blog, but the introductory section was getting too long and I decided to split everything into two articles. So please enjoy this content-light intro to cellular automata (with interactive widgets!).
Most introductions to cellular automata start with Conway's Game of Life, a "zero-player game" with very simple rules. The board consists of a grid of cells, each of which is either alive or dead. On each turn, the board changes as follows: if a dead cell is bordered by exactly 3 living cells it becomes alive, and if a living cell is bordered by less than 2 or more than 3 living cells then it dies.
This can result in some varied and interesting patterns, as you can see for yourself using the widget below:
If you let the widget run for a while, you should eventually see a lot of recurring stationary or periodic paterns showing up, as well as the occasional moving "glider" or "spaceship":
Conway's Game of Life was introduced in 1970 by the mathematician John Conway, and has become one of the most well-known examples of a cellular automaton, a system consisting of a grid of cells and a rule according to which the state of the cells changes over time. It's also Turing complete, meaning that you can (in theory) build a fully-functional computer within the "game", by taking advantage of predictable patterns like the gliders shown above.
There are lots1 of other possible cellular automata that are "lifelike" in the sense that they differ from Life only in terms of the specific number of living neighbours that causes a cell to be born or die. Different rules can result in very different behaviour. I've included a few well-known examples.
Here's the rule known as "Anneal":
Here's "Diamoeba":
Finally, here's "Life Without Death," so named because it's the same as Life except that cells can never die:
Unfortunately, real life is not without death.
John Conway passed away this April due to COVID-19. In the past, Conway has stated that he didn't want to be remembered only for the Game of Life; he has contributed to many other fields, including game theory, group theory, knot theory, theoretical physics, and more, and I don't know enough to cover his many contributions in detail. For that reason, I didn't want to frame this entire article as an obituary or anything like that, but given that I was already writing about cellular automata it seemed necessary to end with a tribute to him.
RIP John Conway.
- Specifically, 262,144 ↩