Conway’s Game of Life is Omniperiodic
Eternal classic
Authors: Nico Brown, Carson Cheng, Tanner Jacobi, Maia Karpovich, Matthias Merzenich, David Raucci, Mitchell Riley
Paper: https://arxiv.org/abs/2312.02799
Happy Saturday!
It has been proven that Conway's Game of Life is omniperiodic, meaning it includes patterns with any period.
For a reminder, the Game of Life is a cellular automaton proposed by British mathematician John Conway in 1970. In the game, cells live on a two-dimensional plane with a square grid, and each cell has 8 neighbors. A cell can be either alive (filled) or dead (empty). The game is turn-based (or generation-based), with the entire field changing at each discrete moment in time according to the rules:
If a dead cell has exactly three live neighbors, it becomes alive.
If a live cell has two or three live neighbors, it stays alive.
In all other cases, a live cell dies.
Here’s a beautiful large-scale run of the Game of Life:
A period is the time after which a cell configuration in the game repeats itself. Such a configuration is called an oscillator.
From the very beginning, simple oscillators were found, such as the 2x2 square block (p1), blinker (p2), pulsar (p3), and glider (which is not quite an oscillator, as it also moves through space, so it's a spaceship). Many of them arise spontaneously from random initial configurations.
For a long time, there was a hypothesis that oscillators of any period >=1 should exist in the Game of Life. It's important to note that this refers to finite oscillators, as infinite ones are straightforward - just create a chain of gliders at the necessary distance.
Oscillators with periods <=15 were discovered manually. In 1996, David Buckingham showed that any oscillator with a period >=61 can be created using Herschel conduits, where a signal is transmitted along a closed path (example). Then the threshold was lowered to 43, finding Snark, a glider reflector at a 90-degree angle.
The unclear part was with periods between 15 and 43, especially with prime numbers. At the start of the millennium, oscillators of periods 19, 23, 27, 31, 34, 37, 38, 39, 41, 43, 51, and 53 were missing. The last ones to be found were periods 19 and 41. But now they have been found, and the Game of Life is proven to be omniperiodic. Time to open the champagne!
Next, I recommend diving into the article. The second chapter provides a wonderful historical description of the searches, which should be read as is, rather than paraphrased. The article also contains clickable images of all the oscillators, leading to an interactive demonstration to play with. My children and I are now spending time there.
The topic of periods is now closed, but other interesting topics are still open. For example, the maximum speed of spaceships. I think Konrad Zuse mentioned something similar in his Rechnender Raum, but it's been a while since I read it; I need to revisit it. In any case, hello to the Theory of Relativity :)
Glider guns of all periods have also not been found yet. Those interested can search for periods 14 ≤ p ≤ 19, and p = 23, 26, 29, 31, 35, 38, 39, 47, 53. There are other interesting topics, such as optimizing oscillators (creating a configuration with the minimum number of cells, the Smallest Known Oscillators of Period p), or strictly volatile oscillators, where each cell pulsates with a given period. Interestingly, SAT solvers are used for these searches, but this is an under-explored topic.
In general, there's excitement even in the classics. We also look forward to developments in the topic of cellular automata, including the modern Lenia family, and the promising approaches to neural cellular automata by our favorite Michael Levin.
Have a great weekend!