Math’s ‘Game of Life’ Reveals Long-Sought Repeating Patterns
Introduction
In 1969, the British mathematician John Conway devised a beguilingly simple set of rules for creating complex behavior. His Game of Life, often referred to simply as Life, unfolds on an infinite square grid of cells. Each cell can be either “alive” or “dead.” The grid evolves over a series of turns (or “generations”), with the fate of each cell determined by the eight cells surrounding it. The rules are as follows:
- Birth: A dead cell with exactly three live neighbors becomes alive.
- Survival: A live cell with two or three live neighbors stays alive.
- Death: A live cell with fewer than two or more than three live neighbors dies.
These simple rules create an astonishingly diverse array of patterns, or “life forms,” that evolve from the many different possible starting configurations of the grid. Lovers of the game have tallied and taxonomized these patterns in an ever-expanding online catalog. Conway discovered a pattern called the blinker, which oscillates between two states.
The next year, he found a much more complicated pattern called the pulsar, which oscillates between three different states.
Soon after oscillators were discovered, the game’s early explorers wondered whether there are oscillators of every period. “At first, we saw only periods 1, 2, 3, 4 and 15,” said the computer programmer and mathematician Bill Gosper, who would go on to discover 17 different novel oscillators over the next several decades. Period 15 oscillators (shown below) came up surprisingly often in random searches.
Surprises lurked for those willing to find them. “From hours and days of viewing, period 5 seemed impossible,” Gosper said. Then in 1971, two years after the game was invented, one was found. Hunting for new oscillators grew into a major focus of the game, a quest bolstered by the advent of computer technology. Accounts of covert searches conducted on office computers have become a cornerstone of the game’s folklore. “The amount of computer time stolen from corporate and university mainframes was staggering,” Gosper said.
Merrill Sherman/Quanta Magazine
Throughout the 1970s, mathematicians and hobbyists filled in the other short periods and found a smattering of longer ones. Eventually, mathematicians discovered a systematic way to build long-period oscillators. But oscillators with periods between 15 and 43 proved tough to find. “People have been trying to figure out the middle for years,” said Maia Karpovich, a graduate student at the University of Maryland. Filling in the gaps forced researchers to dream up a slew of new techniques that pushed the boundaries of what was thought possible with cellular automata, as mathematicians call evolving grids like Life.
Now Karpovich and six co-authors have announced in a December preprint that they have found the last two missing periods: 19 and 41. With those gaps filled, Life is now known to be “omniperiodic” — name a positive integer, and there exists a pattern that repeats itself after that many steps.
The burgeoning community devoted to studying Life, which includes many research mathematicians but also many hobbyists, has found not only oscillators but all kinds of new patterns. They have found patterns that travel across the grid, dubbed spaceships, and patterns that build other patterns: guns, constructors and breeders. They found patterns that compute prime numbers, and even patterns that can execute arbitrarily complicated algorithms.
Oscillators with periods shorter than 15 can be found manually or with rudimentary algorithms that search for oscillators one cell at a time. But as the period gets bigger, so does the complexity, making brute-force searches far less effective. “For small periods, you can search directly,” said Matthias Merzenich, a co-author of the new paper who discovered the first period-31 oscillator in 2010. “But you can’t really go beyond that. You can’t just pick a period and search for it.” (Merzenich earned his doctorate in math from Oregon State University in 2021, but currently works on a farm.)
In 1996, David Buckingham, a Canadian freelance computer consultant and Life enthusiast who had been searching for patterns since the late 1970s, showed that it was possible to construct oscillators of period 61 and higher by sending a pattern around a closed track in an endless loop. By controlling the length of the loop — and the time it took the pattern to complete one round trip — Buckingham found that he could make the period as large as he liked. “It’s chemistry without the funny smells or broken glassware,” he said. “Like building compounds and then exploring the interactions between them.” This meant that, in one fell swoop, he had come up with a way to construct oscillators of arbitrarily long periods, as long as they were longer than 61.
There was a slew of results in the mid-1990s, when many of the missing oscillators between 15 and 61 were discovered through creative combinations of known oscillators, which had been given a swath of colorful names. Caterers were combined with traffic lights, volcanoes spit out sparks, and eaters ate gliders.
By the turn of the 21st century, only a dozen periods were still outstanding. “It seemed very possible to solve this problem,” Merzenich said. In 2013, a new discovery called the Snark loop improved on Buckingham’s 1996 technique and lowered the cutoff above which it was easy to construct oscillators from 61 to 43. This left only five missing periods. One more was discovered in 2019, and two more in 2022, leaving only 19 and 41 — both prime. “Primes are harder because you can’t use small-period oscillators to construct them,” Merzenich said.
Mitchell Riley, a postdoctoral researcher at New York University Abu Dhabi and another co-author of the new paper, has long been intrigued by a type of oscillator called a hassler. “The way hasslers work is, you’ve got an active pattern in the middle and some stable stuff on the outside that reacts with it,” Riley explained. The stable stuff, called a catalyst, is there to nudge the active pattern back into its original state.
Designing them is hard. “All of these patterns are incredibly fragile,” Riley said. “If you put a single dot out of place, they usually just explode.”
Riley created a program called Barrister to look for new catalysts. “What we’re looking for are still lifes that are robust. The whole point is we want them to interact with what’s happening in the middle and then recover,” Riley said.
Riley fed catalysts that Barrister found into another search program that paired them with active patterns. This mostly led to failures, he said. “It’s fairly rare that one of these catalysts survives the interaction. There’s no guarantee of success. You just sort of cross your fingers and hope that you hit the jackpot. It feels a bit like gambling.”
Eventually, his bet paid off. After a few near misses — and a modification to the code that expanded the search to include symmetric patterns — he found a catalyst interaction that could sustain a period-19 oscillator. “People had been trying all kinds of really complicated searches with lots of catalysts and lots of rare active things in the middle, but all that was necessary was finding this new chunky catalyst,” Riley said.
The final missing period, 41, was found by Nicolo Brown, another co-author, who is still an undergraduate math major at the University of California, Santa Cruz. Brown used gliders as catalysts, an idea first proposed by Merzenich.
“We have discovered so much deep behavior over the last 10 years,” Karpovich said. “Everyone’s celebrating for a week — and then moving on to other things. There are so many other problems to solve.” Can oscillators of a given period be made smaller? Can oscillators be found in which every single cell oscillates? Can guns be made with particular periods? Can spaceships be made to travel at particular speeds?
As Buckingham put it, “It’s like being a kid in an infinite toy store.”
