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

31–40 of 114 posts

Re: Building arbitrary Life patterns in 15 gliders

#31

Post by soulofmischief »

biggiemac42 wrote: post #26
soulofmischief wrote: post #23

Earlier quoted context omitted.

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.

I think the portion that is fundamental is deeper than game of life itself. Game of life is a rule set with sufficient complexity to get this far, but it isn't the only one. Anything with this class of behavior will support systems including those resembling DNA, the question is at what scale it emerges. If the scale is too big (arguably the scale for the result in this post is too big), it's a less elegant kind of e…

Agreed. One aspect of CA which interests me is robustness, the ability of a system to recover from error states.

What's been done with GoL is fascinating, but I think the next emergent layer of fascination for me is universal constructors which can handle a certain level of constant distributed noise or interference. A lot of times people just shrug and say, "well this pattern will always be critical/vulnerable in these locations, and cannot be made robust. But to me that opens up the door for entire classes of patterns which measure, embed and repair state of surrounding entities.

Re: Building arbitrary Life patterns in 15 gliders

#34

Post by ivoras »

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...

Re: Building arbitrary Life patterns in 15 gliders

#35

Post by Zenst »

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?

Re: Building arbitrary Life patterns in 15 gliders

#36

Post by bewresu »

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...

...if there's a GoL version where time varies somehow¹ with something²

¹ directly?

² amount of activity? mass?

Re: Building arbitrary Life patterns in 15 gliders

#37

Post by Strilanc »

OscarCunningham wrote: post #28
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!

There are still plenty of open problems! Here are some of my favourites: * Is there an oscillator of every possible period? (We have them all except 19 and 41.) * If you start off the entire plane in a random starting state, does its density tend to a limit as time goes to infinity? * Is there a 'phoenix' oscillator, in which every live cell dies every generation, of period greater than 2? * Can every pattern be dest…

I'd be surprised if there was a computable density limit for the random plane, just because the system is Turing complete so the answer could easily end up being like Chaitin's contant where it depends on halting problems. For example, note that an infinite random plane will contain, with probability 1, purely-by-chance prebuilt artificial intelligences with goals like "maximize number of blinkers in the plane". Though I guess it's also an open question if such a system could even survive and spread, as opposed to just getting eventually crushed by the surrounding noise.

Re: Building arbitrary Life patterns in 15 gliders

#38

Post by enkid »

OscarCunningham wrote: post #25
NeoTar wrote: post #17

Do we have any idea / intuition about what proportion of patterns are build-able? If not on an infinite grid, then some subset (i.e. 100% of 1x1 patterns are build-able, 80% of 3x3 patterns, 60% of 5x5 patterns, etc.)

There exists an 'orphan' pattern that cannot arise in any configuration after the first generation. When we look at large patterns, the proportion of them that contain an orphan tends to 1. On the other hand the smallest known orphan is 12 by 8, and we also know that all still lifes (unchanging patterns) with up to 21 cells can be built.

21 cells would be a 3 by 7?

Re: Building arbitrary Life patterns in 15 gliders

#39

Post by OscarCunningham »

Strilanc wrote: post #37
OscarCunningham wrote: post #28

Earlier quoted context omitted.

There are still plenty of open problems! Here are some of my favourites: * Is there an oscillator of every possible period? (We have them all except 19 and 41.) * If you start off the entire plane in a random starting state, does its density tend to a limit as time goes to infinity? * Is there a 'phoenix' oscillator, in which every live cell dies every generation, of period greater than 2? * Can every pattern be dest…

I'd be surprised if there was a computable density limit for the random plane, just because the system is Turing complete so the answer could easily end up being like Chaitin's contant where it depends on halting problems. For example, note that an infinite random plane will contain, with probability 1, purely-by-chance prebuilt artificial intelligences with goals like "maximize number of blinkers in the plane". Thou…

Right, but I'm hoping it might be possible to prove that the limit exists (even if it's an uncomputable number), as opposed to some oscillating behaviour where the density infinitely often goes up to 70% and then back down to 30% for example.

Re: Building arbitrary Life patterns in 15 gliders

#40

Post by OscarCunningham »

enkid wrote: post #38
OscarCunningham wrote: post #25

Earlier quoted context omitted.

There exists an 'orphan' pattern that cannot arise in any configuration after the first generation. When we look at large patterns, the proportion of them that contain an orphan tends to 1. On the other hand the smallest known orphan is 12 by 8, and we also know that all still lifes (unchanging patterns) with up to 21 cells can be built.

21 cells would be a 3 by 7?

Gardens of Eden can be arbitrary patterns, whereas only the 21-cell still lifes are known to be constructible.
Post reply on HN