Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Building arbitrary Life patterns in 15 gliders

btm.qva.mybluehost.me

Post reply on HN
Print view View original

51–60 of 114 posts

Re: Building arbitrary Life patterns in 15 gliders

#51

Post by dvgrn »

Zenst wrote: post #35
biggiemac42 wrote: post #12

Hi there, I'm the author (of the blog post, not of the achievement itself)! So glad this is spreading. Feel free to ask here or on the post for more clarification if stuff is too unclear

Do you see this as a form of geometric compression in the future?

It's a bit hard to see how this RCT trick could be useful for reducing anything besides the number of gliders.

RCT is basically one very unreasonable end of a wide spectrum: you can use a very small number of gliders to build something, as long as you're content to have the construction take a ridiculously long time. Conversely, you can build that same thing in a lot less time, but it will take a lot more gliders.

Re: Building arbitrary Life patterns in 15 gliders

#52

Post by galaxyLogic »

soulofmischief wrote: post #23
squaredot wrote: post #10

This result is really beautiful! At the same time, it's like GoL has been conquered, and in that it leaves me a little sad. But just a little bit. Congratulations!

This "conquering" is all just proof as to the fundamental nature of the Game of Life. It's not hard to imagine a working system of walking proteins and unzipping DNA structures in light of these findings. It really is beautiful.

Very interesting. A biological cell is a 3-D self-replicating pattern (or is it 2-D rather?). Does GoL give us some insight into the nature of biological cells?

Re: Building arbitrary Life patterns in 15 gliders

#53

Post by geysersam »

dvgrn wrote: post #51
Zenst wrote: post #35

Earlier quoted context omitted.

Do you see this as a form of geometric compression in the future?

It's a bit hard to see how this RCT trick could be useful for reducing anything besides the number of gliders. RCT is basically one very unreasonable end of a wide spectrum: you can use a very small number of gliders to build something, as long as you're content to have the construction take a ridiculously long time. Conversely, you can build that same thing in a lot less time, but it will take a lot more gliders.

Also, even if the maximum number of gliders is fixed (15), that does not imply any limit on the amount of information needed to store their positions.

The glider positions might very well require more storage than the desired pattern itself.

Re: Building arbitrary Life patterns in 15 gliders

#54

Post by dvgrn »

andrepd wrote: post #49
ivoras wrote: post #34

Interestingly enough, the concept of placing gliders at a distance away seems to touch on the relativity of space and time. Here, with space, we are also encoding the time at which a certain pattern (a glider) appears where it's needed. In a rigid system like the GoL, we can't trade space with time easily, since everything happens at a constant speed, but it makes one wonder...

How does it "touch on relativity of space and time"?

I think that was just saying "more space between initial gliders implies a longer time needed to complete construction". There's no Einsteinian relativity to be found here.

(A Doppler effect does show up in Conway's Life sometimes, but that's about as far as we get with analogies to the physical universe...!)

Re: Building arbitrary Life patterns in 15 gliders

#55

Post by dvgrn »

geysersam wrote: post #53
dvgrn wrote: post #51

Earlier quoted context omitted.

It's a bit hard to see how this RCT trick could be useful for reducing anything besides the number of gliders. RCT is basically one very unreasonable end of a wide spectrum: you can use a very small number of gliders to build something, as long as you're content to have the construction take a ridiculously long time. Conversely, you can build that same thing in a lot less time, but it will take a lot more gliders.

Also, even if the maximum number of gliders is fixed (15), that does not imply any limit on the amount of information needed to store their positions. The glider positions might very well require more storage than the desired pattern itself.

That's definitely completely true. We can specify the relative positions of the initial gliders at each of the three corners of the RCT pattern in just a few dozen bytes.

But the number that says how far apart those corners are from each other has very roughly half a million digits. The exact number depends on exactly what pattern is being encoded by the RCT pattern -- I think the example construction of Alan Hensel's decimal counter pattern needs somewhere around a 450,000-digit number.

There are some optimizations underway to decrease that number by a few percentage points, but it's always going to be a very big number!

Re: Building arbitrary Life patterns in 15 gliders

#56

Post by eurasiantiger »

anderskaseorg wrote: post #7
eurasiantiger wrote: post #3

The 15 is strangely familiar. Hypothesis: if the interaction of any pair of oscillators can theoretically be represented by a single oscillator, this could also be possible with 4 and 6 (larger) gliders, simply because (4 over 2) = 6, (6 over 2) = 15. The above may only hold in a continuous-valued GoL, or it may not hold at all.

There’s no “larger glider”. The name “glider” refers to a single specific pattern of five cells. https://en.wikipedia.org/wiki/Glider_(Conway%27s_Life)

True. I was thinking about spaceships and other oscillating movers.

Re: Building arbitrary Life patterns in 15 gliders

#57

Post by dvgrn »

Zenst wrote: post #33

Interesting when you think about DNA and how that shapes things. Equally, compression, is this an avenue worth exploring and a whole new way of doing things awaiting to be tapped?

Heh, oddly enough, the RCT can probably be better thought of as a way of explosively _decompressing_ a glider construction recipe. There are lots and lots of reasonable-sized recipes for constructing different patterns. When you apply the RCT trick to any of them, the cost in gliders always shrinks to 15, but the pattern's bounding box always expands to something gargantuan.

The Life pattern that most evokes DNA and self-replication is another megapattern from several years ago, the 0E0P metacell, which even has a visible "nucleus" for its "DNA":

  https://conwaylife.com/wiki/0E0P_metacell

Re: Building arbitrary Life patterns in 15 gliders

#58

Post by westurner »

dvgrn wrote: post #43
bewresu wrote: post #36

Earlier quoted context omitted.

...if there's a GoL version where time varies somehow¹ with something² ¹ directly? ² amount of activity? mass?

There have been a lot of GoL variants over the years, but I don't remember running into any attempts to vary the speed of evolution in different locations on the same grid. The idea that all neighbors move to the next tick simultaneously is a fundamental assumption in cellular automata in general. If you try changing that, the optimizations that allow us to simulate CAs at any kind of reasonable speed ... all stop wo…

The "superstep" that we practically impose upon simulations of entropy and emergence is out of accord with our modern understanding of non-regularly-quantizable spacetime. The debuggable Von Neumann instruction pipeline precludes "in-RAM computing" which conceivably does converge if consensus-level error correction is necessary.

Re: Building arbitrary Life patterns in 15 gliders

#59

Post by dvgrn »

pfortuny wrote: post #4

This is awesome. This result would fit perfectly well in Wolfram's NKS. The next question is... is this the minimum?

15 is probably not the minimum. There are some ideas floating around for getting down to 14, and some wilder ideas that might get to 13 or 12.

Below that we'd need some significantly different mechanism that nobody has thought of yet. It doesn't seem likely that anyone will be able to prove that universal construction is impossible with a single-digit number of gliders -- but if a solution exists it might take an omniscient being to find it.

... Or maybe some clever hacker will figure it out tomorrow! That's what happened to get us to the current minimum. We were stuck at a minimum of 32 for quite a while, until Daniel Vargas (MathAndCode) suddenly showed up with a new idea.

Re: Building arbitrary Life patterns in 15 gliders

#60

Post by hansworst »

dvgrn wrote: post #43
bewresu wrote: post #36

Earlier quoted context omitted.

...if there's a GoL version where time varies somehow¹ with something² ¹ directly? ² amount of activity? mass?

There have been a lot of GoL variants over the years, but I don't remember running into any attempts to vary the speed of evolution in different locations on the same grid. The idea that all neighbors move to the next tick simultaneously is a fundamental assumption in cellular automata in general. If you try changing that, the optimizations that allow us to simulate CAs at any kind of reasonable speed ... all stop wo…

Well, there is SmoothLife (e.g. https://www.arxiv-vanity.com/papers/1111.1567/#S4) where the time step is also made continuous. I suppose you could extend this so that this isn't some uniform value across the entire space, but instead a value that is constantly recomputed based on neighbourhood density.
Post reply on HN