Build arbitrary life models in 15 gliders

Conway's Game of Life community celebrated a historic achievement on November 9, 2022. An idea in the making for years, the "Reverse Caber Tosser" design finally had all the pieces necessary to achieve its stated goal.

>

This goal is simple. Select any pattern that can be built in Life - for example, the water bear. Start with a small number of gliders (now 15) in an otherwise empty Game of Life universe. After enough time, those gliders should build that model. No extra debris, no misplaced scaffolding, just a pure synthesis of whatever you've chosen.

This article will explain how it works, how we got here, and why it's so cool.

How is it possible?

From an information theory perspective, an arbitrarily selected model can have unlimited complexity. Each of these models requires a different initial set of pads.

With 15 gliders (or any fixed number), the only difference between an initial set and another is where they start. Since we have an infinite number of patterns to create, we need to list an infinite number of arrangements of 15 gliders. It is possible, but only by taking advantage of a corresponding unlimited distance between at least one pair of gliders in the recipe.

With this constraint comes a little hope. The fact that we have to use a lot of distance guides us to our first principle. The distance itself encodes the information.

The invitation to make people think about this came in 2015, in a really weird way.

Doubtful beginnings

It all started with Gustavo, a Conway Game of Life enthusiast from Brazil who tended to stray off topic on the forums. In a new thread, Gustavo talked about a secret MIT Morse code signal he was decoding, which seemed to discuss "Game of Life - Spaceship Synthesis Research". The community's interaction with this thread was honestly hilarious. Some people try to please Gustavo, asking for proof, others try to make the inconsistencies in his story more obvious.

Everything about this story was just imaginative nonsense, without substance. User "gameoflifeboy" described it as "the weirdest forum thread so far in 2015". But a part got stuck. Gustavo said that through his eavesdropping he learned that a previously unknown spacecraft larger than the Caterpillar had a 386 glider synthesis.

Adam Goucher, a mathematician of some notoriety and author of the cp4space blog, considered this plausible. Originally not plausible, as the story was just the brainchild of an internet troll. Rather, it is plausible that a super-complex model could be synthesized in a relatively small number of gliders. In his words:

As long as we can synthesize a universal constructor in 385, the entire plane could be encoded in the *distance* between the final glider and the constructor (by Godel coding or whatever).

Adam Goucher Universal Constructor

Universal constructors also appeared in my article on Waterbear. I will try to treat the subject a little better this time, by analogy with Turing machines.

We often hear that a Turing machine is just as powerful as a modern computer, in that it can run all the same algorithms (but perhaps taking longer). And similarly, we often hear that much weaker systems, like Rule 110, are just as powerful as a Turing machine. Although neither the most nor the least efficient example of a computer, the Turing machine is the canonical basis of computational ability. Any system with equivalent computing capacity is considered "Turing Complete".

Returning to Conway's Game of Life, replace calculation with construction. Systems are equivalent if they can build all the same things, regardless of their efficiency. For a canonical baseline, we can use arbitrary collections of gliders converging from infinity, as in the model below synthesizing a "weekender" spaceship.