All 23-Bit Still Lifes Are Glider Constructible

Summary

In the Game of Life, which still lifes can be produced by crashing gliders together? We’ve known for a few years that the answer cannot be “all of them”, because in 2022 Ilkka Törmä and Ville Salo found a patch of still life that, if it exists in the universe, must have existed since the beginning of time. And so, there is no way we could have produced it out of empty space through glider collisions. Similar such patches have been found since, with the goal of optimising size or population, and at the time of writing the record holder is an unsynthesizable still life with population 154 produced by forum user “400spartans”. Finding syntheses for small still lifes is easy, but at some unknown point below 154 it becomes impossible. Today, we completed our collaborative project to notch the lower bound up from 22 to 23, by giving explicit syntheses for all 1,646,147 (strict)A still life is strict when all its islands are necessary to maintain the stability of the pattern. still lifes with population 23. The final holdout shown below has systematic name xs23_g88m9icz1iu146, and was solved by vilc. As you might imagine, this is not the first project of this kind; all still lifes with 18 bits were synthesised in October 2019, 19 bits in February 2020, 20 bits in March 2021, 21 bits in November 2022 and 22 bits in August 2024. As the number of bits increases, the number of distinct still lifes explodes exponentially, so that the 23-bit project had about 2.4× as many still lifes to consider as the 22-bit project. The situation is actually worse than that: not only are there more problems to get through, but each additional bit reveals knotty new ways for a still life to fit together. My contribution was the mass generation of synthesis recipes through computer searches. These disposed of roughly 99.97% of the targets, letting the people with actual synthesis talent focus on the ones where new ideas were needed. I’ll spend the rest of the post talking about the things I trie...