Building arbitrary Life patterns in 15 gliders • Hacker News Board

Re: Building arbitrary Life patterns in 15 gliders

#81

Post by OscarCunningham » Wed, Nov 30, 2022, 3:14 PM UTC

JKCalhoun wrote: post #80

biggiemac42 wrote: post #20

Earlier quoted context omitted.

This is a really good and not at all easy to answer question. The most I can say is that folks earlier this year used some SAT solver equivalent to find notable patterns that cannot be constructed - including a still life and an oscillator https://conwaylife.com/wiki/Unsynthesizable_oscillator_1 . This doesn't have much bearing on the probability of constructability for an arbitrary large pattern.

Yeah, I was wondering, with todays computing power, if it were possible to run outrageously large random Life universes and use some sort of software to look for "interesting patterns" (whatever that means). Or are these "discoveries" being done by hand?

A lot of discoveries have come from 'soup search' where you start with a random 16 by 16 square and let it evolve. We've run over 156 trillion soups https://catagolue.hatsya.com/statistics. This tends not no produce complicated machines, but rather small components that can then be engineered into larger patterns.

Re: Building arbitrary Life patterns in 15 gliders

#82

Post by iamgopal » Wed, Nov 30, 2022, 3:33 PM UTC

What’s most complex thing achieved in GOL ?

Re: Building arbitrary Life patterns in 15 gliders

#83

Post by OscarCunningham » Wed, Nov 30, 2022, 3:38 PM UTC

iamgopal wrote: post #82

What’s most complex thing achieved in GOL ?

Probably either this or the 0E0P metacell https://conwaylife.com/wiki/0E0P_metacell, a large pattern which makes copies of itself in a way that mimics another cellular automaton, or Life itself.

Re: Building arbitrary Life patterns in 15 gliders

#84

Post by vanderZwan » Wed, Nov 30, 2022, 4:05 PM UTC

Whenever I read one of these deep dives into GoL achievements, and let me preface this by saying I mean this as a compliment, I feel like I'm reading the extended universe lore on a wiki page for a giant fantasy franchise. It's maths but feels so much more narratively rich than most other mathematics somehow, and the community around it has such a unique subculture vibe to it too.

Re: Building arbitrary Life patterns in 15 gliders

#85

Post by VikingCoder » Wed, Nov 30, 2022, 4:08 PM UTC

vanderZwan wrote: post #84

Whenever I read one of these deep dives into GoL achievements, and let me preface this by saying I mean this as a compliment, I feel like I'm reading the extended universe lore on a wiki page for a giant fantasy franchise. It's maths but feels so much more narratively rich than most other mathematics somehow, and the community around it has such a unique subculture vibe to it too.

Have you read "Permutation City"? I'm definitely reminded of it every time.

Re: Building arbitrary Life patterns in 15 gliders

#86

Post by tiborsaas » Wed, Nov 30, 2022, 4:15 PM UTC

Absolutely mind blowing result, looking at the video at the bottom is so hard to comprehend there's no human interaction in this besides setting up the 15 gliders.

At 1:57 it even looks like someone draws a line casually with a mouse.

Re: Building arbitrary Life patterns in 15 gliders

#87

Post by OscarCunningham » Wed, Nov 30, 2022, 4:18 PM UTC

vanderZwan wrote: post #84

Whenever I read one of these deep dives into GoL achievements, and let me preface this by saying I mean this as a compliment, I feel like I'm reading the extended universe lore on a wiki page for a giant fantasy franchise. It's maths but feels so much more narratively rich than most other mathematics somehow, and the community around it has such a unique subculture vibe to it too.

This is the legacy of Conway (who invented Life) and Gardner (who popularised it).

Re: Building arbitrary Life patterns in 15 gliders

#88

Post by isoprophlex » Wed, Nov 30, 2022, 4:24 PM UTC

I had a particularly hard time grokking the way the semilator works to reduce pattern size. It's a pretty difficult term to google too, being so similar to the word 'simulator'. Does anyone well versed in GoL-ogy care to share a short ELI5?

Edit: thanks you people for the explanation, makes sense. Nice hack to make it feasible.

Re: Building arbitrary Life patterns in 15 gliders

#89

Post by biggiemac42 » Wed, Nov 30, 2022, 4:44 PM UTC

tromp wrote: post #79

This is an incredible achievement. The most impressive piece of GoL engineering I've ever seen! Clearly, number of gliders is no longer a good measure of complexity of constructions. Perhaps one should fix a straightforward way to encode a set of gliders by position (e.g. using [1]) and orientation and take the minimum number of bits of such a description. Just one question: > 1274729 – build a DBCA and pass control…

Ooh, I appreciate the diligence! The numbers here came from manually fiddling with more granular output from Pavgran's special purpose "profiler" script. One of those steps, where the DBCA assumes control of the bit stream, takes 1615 gliders. I would bet I made a mistake and added it twice, probably to both the DBCA building and the task of the DBCA itself. It belongs in only one of them!

I can verify this later.

Re: Building arbitrary Life patterns in 15 gliders

#90

Post by biggiemac42 » Wed, Nov 30, 2022, 4:56 PM UTC

isoprophlex wrote: post #88

I had a particularly hard time grokking the way the semilator works to reduce pattern size. It's a pretty difficult term to google too, being so similar to the word 'simulator'. Does anyone well versed in GoL-ogy care to share a short ELI5? Edit: thanks you people for the explanation, makes sense. Nice hack to make it feasible.

Right, as far as I can tell the term "semilator" was coined for this task, so google won't help.

The middle of the RCT pattern where all of the action happens, reads its first bit 2^N generations B.S (before singularity, or before splat, whichever you prefer). Next bit is 2^(N-1) B.S. Next would be 2^(N-2), but this is what the semilator changes.

During the franky enormous gap between 2^(N-1) and 2^(N-2) generations B.S, extra spaceships come in at an orthogonal direction. These have two possible configurations, giving equivalent results to either of the possible bit reads. This accelerates the speed of bit reading, and means that N of millions can be emulated by a pattern with N less than 30. Much less initial distance, much less time. The addition of millions of cells of spaceships doesn't make the overall pattern smaller in an informational sense, just in the scale of time and distance between its constituent parts.