Back in 1970, the mathematician John Conway created a game with no players that evolves entirely from its initial state. The game is set in a kind of computational universe called a cellular automaton. This universe consists of an infinite grid of squares that can be alive or dead and that, at each time step, can flip from one state to the other according to the states of the squares around it.
This cellular automaton has since become known as Conway’s Game of Life and famous for the extraordinary complexity that emerges within it. This computational universe is home to beacons that flash, pulsars that beat time and “gliders” and “spaceships” that fly across the computational sky. Computer scientists have shown that this world can house computers in the form of universal Turing machines and replicators that can produce exact copies of themselves.
Step Change
Indeed, nobody is quite sure where the limits lie for the Game of Life and computer scientists are still wrestling with numerous unsolved problems. One of these relates to the periodicity of the patterns in this universe. It has long been clear that some patterns do not change over time, in other words they have a periodicity of one time step. Others repeat every two steps or three or four or five steps.
Then in the 1990s, it became clear it was possible to produce patterns with any periodicity greater than or equal to 61 time steps. Mathematicians proved this by sending patterned signals along tracks that form loops. The smallest possible loop can be traversed in 43 steps. By increasing its size, mathematicians can make patterns repeat over any number of time steps.
This raises an interesting question. Is it possible to make patterns that repeat over all possible periods? In other words, is the Game of Life omniperiodic?
Given the proof above, this boils down to the problem of finding oscillating patterns that repeat for every period from 1 to 43. The first few were relatively easy to find. “Periods in the “missing middle”, 15 < p < 43, particularly those that are prime, proved more difficult to find,” say Mitchell Riley, at New York University in Abu Dhabi and colleagues.
But as work continued, researchers began to fill the gaps. “At the turn of the millennium, only twelve periods remained to be found: 19, 23, 27, 31, 34, 37, 38, 39, 41, 43, 51 and 53,” they say.
In this century, computer scientists found all these oscillators, except two: 19 and 41.
Now Mitchell and co announce the work is done. “The search has finally ended, with the discovery of oscillators having the final two periods,” they say. This proves once and for all that the Game of Life is indeed omniperiodic.
Mitchell and co’s paper describes all 43 of these oscillators along with the techniques that computer scientists and mathematicians have developed to find them and build ever more capable oscillators.
They point out that the omniperiodicity problem has been a focal point for research into the Game of Life. This work has led to a vast number of techniques, tools and approaches for exploring and characterizing this computational universe.
But now that the problem is solved, what next? Mitchell and co point to numerous unsolved problems that could provide a similar focal point for researchers. They say the spaceship velocity problem is perhaps the most significant.
Spaceship Velocities
A spaceship is a pattern that reoccurs at another location from its original position. In other words, it translates across the computational sky. (Ordinary oscillators can be thought of as stationary spaceships.)
Bearing in mind that nothing can travel through the grid faster than one unit cell per unit time, the authors say there are good reasons to think that all possible rational spaceship velocities ought to be possible.
However, that leaves open the question of “which of the theoretically possible spaceship velocities can be realized,” they say.
Then there is the problem of finding the smallest oscillators of a given period. Many of the first to be discovered for each period are no longer the smallest, they say. The challenge of finding smaller ones remains for many periods.
There are plenty of other open problems. As Mitchell and co finally conclude: “Life’s work is never done!”
Ref: Conway's Game of Life is Omniperiodic : arxiv.org/abs/2312.02799
