Everything in Conway's Game of Life can be constructed from 15 gliders

November 30, 2022 7:41 AM

The first pattern that most people learn in Conway's Game of Life is the diagonally-moving glider. Over the decades, Life enthusiasts have found that many other patterns can be constructed from gliders, by positioning enough of them to hit each other in the right way - sometimes thousands of them. Just a couple of weeks ago, it was finally demonstrated that you can construct all these other patterns from just 15 gliders... you just might need to start them really far apart. So far, in fact, that the distances between them are measured in millions of binary digits: enough to encode a two-stage constructor, the design itself, and a cleanup mechanism. Math blogger biggiemac42 explains how it was done: at the end of the post is a video of it in action.
posted by automatronic (20 comments total)

Do you want gray goo? Because that's how you get gray goo.
posted by Kyol at 8:30 AM on November 30, 2022 [6 favorites]

That's amazing!
posted by the antecedent of that pronoun at 8:56 AM on November 30, 2022

Do you want gray goo? Because that's how you get gray goo.

Or universal consciousness.
posted by mhoye at 9:04 AM on November 30, 2022

So…. Does this mean that the Game of Life is a universal Turing machine?
posted by njohnson23 at 9:04 AM on November 30, 2022

Computers have already been built in Life, and could be constructed using this method.

Simulationists can now look forward to being 15 gliders for most of eternity.
posted by joeyh at 9:07 AM on November 30, 2022 [4 favorites]

You spawn 15 gliders, what do you get?
Another generation older and deeper in HashLife memory-debt.
St. Conway, don't you call me 'cause I can't go
I owe my soul to the Golly store
posted by genpfault at 9:16 AM on November 30, 2022 [5 favorites]

So…. Does this mean that the Game of Life is a universal Turing machine?

There have been working Turing machines in Life for over twenty years. You can also play Life inside Life using metapixels.
posted by automatronic at 9:23 AM on November 30, 2022 [7 favorites]

Do you want gray goo? Because that's how you get gray goo.



given the number of steps involved, there's no way molecules or systems in matter could ever approach this level of complexity from such simple fragile beginnings because of error rates.

the minimal glider system is awesome! but the minimal glider system is fragile - it is not robust to a single error on path AT ALL.

in silico systems like this can have effectively zero error rates with models like this because the bits in the glider aren't REAL (quantum or other tiny) bits, they are simulations in programs with amazing physical/code redundancy. these simulated bits would lead to error rates like less than 1/10^20 (pulling that number out of my ass, but it seems OK?) in a deterministic program like this!


biology has a pretty impressive error correction. but that's done with redundancy, not with (effectively) infinitely faithful copying like in the sim above. doing these gliders with nanotech or biology (but I repeat myself) will get you NOWHERE.
posted by lalochezia at 9:26 AM on November 30, 2022 [4 favorites]

At some point in the mid 1980s I spent probably 100 hours messing with Life. We had a Macintosh with some Life app. I could easily do that 100 hours again now.
posted by neuron at 11:33 AM on November 30, 2022 [2 favorites]

Grey Goo is the new Dark Enlightenment.
posted by CynicalKnight at 12:06 PM on November 30, 2022

They can make any pattern? Even Eden patterns?
posted by plinth at 1:03 PM on November 30, 2022 [2 favorites]

I've certainly been aware of GoL and played around a long while ago but wow, it just keeps growing. By it I meant the community of lifers(?)

Here's a fun pattern that runs in a browser: grow-by-one_object
posted by sammyo at 2:11 PM on November 30, 2022 [1 favorite]

Any constructable pattern; Eden patterns are not constructable.
posted by phooky at 2:22 PM on November 30, 2022 [6 favorites]

I once read a story about storing an arbitrarily large amount of information as a single mark on a rigid rod (wizard's staff, alien crystal, or some such). You recovered the bit string by measuring the lengths above and below the mark, and expressing their ratio as a binary fraction. Of course this is good for only a few bits with real materials and measurements. But on the perfect grid of Conway's Life, it is exactly how the positions of a few gliders can encode millions of bits! Incredible work.
posted by drdanger at 2:38 PM on November 30, 2022 [6 favorites]

Obligatory xkcd "A bunch of rocks".
posted by aleph at 2:50 PM on November 30, 2022 [2 favorites]

> I once read a story about storing an arbitrarily large amount of information as a single mark on a rigid rod (wizard's staff, alien crystal, or some such). You recovered the bit string by measuring the lengths above and below the mark, and expressing their ratio as a binary fraction.

Arithmetic coding?
posted by genpfault at 3:47 PM on November 30, 2022 [2 favorites]

I only know of Life through the David Brin novel Glory Season - but this is definitely a strategy those characters would want to know.
posted by rednikki at 5:16 PM on November 30, 2022

Life is already here, it's just not evenly distributed.
posted by Western Infidels at 5:44 PM on November 30, 2022

> Arithmetic coding?

Yes! To me the gliders feel like they exist in physical space (like the notch on the wizard's staff) although ultimately it's all coded strings of symbols.
posted by drdanger at 8:32 PM on November 30, 2022 [1 favorite]

Well this is delightful.
posted by cortex at 1:15 PM on December 1, 2022