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

21–30 of 114 posts

Re: Building arbitrary Life patterns in 15 gliders

#21

Post by biggiemac42 »

abetusk wrote: post #5

The basic idea is to use the distance of the gliders to encode information, so when they hit each other allows for an embedding of a Turing machine. I'm no expert here but some basic ideas are that some small number of gliders (two?) can hit each other and produce a "glider gun", allowing for just a few gliders to "upgrade" to producing a steady stream of gliders. There's a "Reverse Caber Tosser" (RCT) structure whic…

To clean up the mistakes in your summary:

4 gliders hit each other to make a stream of gliders. This isn't a gun, because a gun costs more. instead it's a GPSE, which looks like a gun from the barrel end, but has a limit. As it approaches that limit, the RCT mechanism lets another three GPSEs generate an arbitrary list of bits, controlled by the precise location of the first (as a binary number). The final count 15 comes from the naive 4×4 minus one from being able to piggyback one of the constructions off a neighbor to save a single glider.

From bits to an embedded turing machine is gol magic that the blog post treats better than my comment could.

Re: Building arbitrary Life patterns in 15 gliders

#22

Post by chriswarbo »

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 are "garden of eden" patterns which can only exist as an initial configuration: there is no pattern which evolves into a garden of eden, hence there can be no constructor capable of building them https://en.wikipedia.org/wiki/Garden_of_Eden_(cellular_autom...

If we limit ourselves to glider interactions, the article links to the following patterns which cannot be constructed (including garden of eden patterns): https://conwaylife.com/wiki/Category:Patterns_that_can_not_b...

Re: Building arbitrary Life patterns in 15 gliders

#23

Post by soulofmischief »

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.

Re: Building arbitrary Life patterns in 15 gliders

#25

Post by OscarCunningham »

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.

Re: Building arbitrary Life patterns in 15 gliders

#26

Post by biggiemac42 »

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.

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

Re: Building arbitrary Life patterns in 15 gliders

#27

Post by biggiemac42 »

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)

LMAO I found outdated info on that wikipedia page, in the best way.

"Some patterns require a very large number (sometimes hundreds) of glider collisions"

Re: Building arbitrary Life patterns in 15 gliders

#28

Post by OscarCunningham »

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 destroyed by bombarding it with gliders?

* Is there an indestructible pattern?

At the moment people are working on building a spaceship which is only 1 cell tall in its starting state: https://conwaylife.com/forums/viewtopic.php?f=2&t=2040.

Re: Building arbitrary Life patterns in 15 gliders

#30

Post by chriswarbo »

anoncow wrote: post #8

As a lay Comp Sci person I am wondering what this translates into? What implication does this have?

The principle is the same as von Neumann's "universal constructor", so it doesn't really prove anything we didn't know in theory.

However, von Neumann's design uses a cellular-automaton with many more rules, and those were specifically chosen to help define that constructor (Langton Loops are a more extreme example of choosing rules to make construction easier). In constrast, the rules for Game of Life (GoL) were chosen to be simple and interesting, not fine-tuned for any particular patterns (for an even simpler set of rules, see the Rule 110 cellular-automaton).

We know the GoL is Turing-complete, so it can emulate any computable system; including those other cellular-automata, e.g. von Neumann's universal constructor. Such emulations will typically use a large GoL pattern to represent each emulated cell (e.g. see "life in life"): if we emulate a universal constructor, we can use it to assemble any pattern of those emulated cells. We could also emulate GoL inside some other cellular-automaton, and hence use a universal constructor to assemble any pattern of emulated GoL cells. But the question still remains: can we assemble any pattern of "native" GoL cells? That's what the constructors in the article are doing (at least, for a broad class of patterns).

The rest is a matter of "code golf", trying to make the patterns smaller and faster (and indeed feasible to run on a real PC!)

https://en.wikipedia.org/wiki/Von_Neumann_universal_construc...

https://en.wikipedia.org/wiki/Langton%27s_loops

https://en.wikipedia.org/wiki/Rule_110

https://conwaylife.com/wiki/Turing_machine

https://conwaylife.com/wiki/Unit_cell

Post reply on HN