News for hackers. Stuff that matters.
Re:In Game of Life any buildable pattern can be constructed ... by NeoTar on Wednesday November 30, 2022 @04:45AM (#33798752)
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.)

Re:In Game of Life any buildable pattern can be constructed ... by chriswarbo on Wednesday November 30, 2022 @05:18AM (#33798944)
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:In Game of Life any buildable pattern can be constructed ... by knome on Wednesday November 30, 2022 @08:29AM (#33800390)
I wonder if you could bypass this with a level of indirection.

If the GoL wizards can construct an expanding and initially configurable 'GoL in GoL' grid [1], they could configure the 'garden of eden' as the initial configuration for their 'GoL in GoL' simulation.

It's not the same thing, of course, but it would allow you to run Garden of Eden patterns still starting with just your initial 15 gliders.

To construct a garden of eden pattern, you must first construct the universe :)

[1] similar to https://www.youtube.com/watch?v=xP5-iIeKXE8

Re:In Game of Life any buildable pattern can be constructed ... by chriswarbo on Wednesday November 30, 2022 @08:48AM (#33800665)
Sure, we can build them with "meta cells"; but that's just emulation (the same way a SNES emulator doesn't make my laptop a SNES).

We already have GoL turing machines (with "tape factories" that travel faster than the read/write head); we could likewise use those to emulate GoL with arbitrary input, just by setting up an appropriate "tape". The result is far less pretty though ;)

I touched on this in a sibling comment: https://news.ycombinator.com/item?id=33799084

Re:In Game of Life any buildable pattern can be constructed ... by OscarCunningham on Wednesday November 30, 2022 @05:28AM (#33798993)
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:In Game of Life any buildable pattern can be constructed ... by enkid on Wednesday November 30, 2022 @06:21AM (#33799292)
21 cells would be a 3 by 7?
Re:In Game of Life any buildable pattern can be constructed ... by OscarCunningham on Wednesday November 30, 2022 @06:26AM (#33799320)
Gardens of Eden can be arbitrary patterns, whereas only the 21-cell still lifes are known to be constructible.
Re:In Game of Life any buildable pattern can be constructed ... by enkid on Wednesday November 30, 2022 @06:33AM (#33799361)
Ok, but what do you mean by a "still life" of 21 cells? Is that a rectangle in a larger field or is it an arbitrary set of cells?
Re:In Game of Life any buildable pattern can be constructed ... by OscarCunningham on Wednesday November 30, 2022 @06:43AM (#33799431)
A pattern with 21 live cells in any bounding box.
Re:In Game of Life any buildable pattern can be constructed ... by enkid on Wednesday November 30, 2022 @06:49AM (#33799464)
Thanks for answering!
Re:In Game of Life any buildable pattern can be constructed ... by dvgrn on Wednesday November 30, 2022 @07:58AM (#33800023)
(Not just any such pattern, though -- a still life also means that it doesn't change when you evolve it according to Life rules.)
Re:In Game of Life any buildable pattern can be constructed ... by OscarCunningham on Wednesday November 30, 2022 @08:06AM (#33800107)
Also we can only do the strict still lives (i.e. those which are connected https://conwaylife.com/wiki/Still_life#Strict_still_lifes). We can't necessarily put down a 10-cell still life and an 11-cell still life near to each other.
Re:In Game of Life any buildable pattern can be constructed ... by dvgrn on Wednesday November 30, 2022 @08:37AM (#33800501)
Heh, not necessarily, that's true, in the sense that all the possible arrangements haven't been tested and shown to be constructible.

On the other hand, pseudo-still-life and quasi-still-life arrangements are much easier to construct on average than strict still lifes with the same number of cells.

I think the consensus is that someone could figure out how to construct any given stable 21-bit configuration. The non-strict cases are just a bit too numerous and not interesting enough, so nobody has gone through and formally checked them off the list.

Re:In Game of Life any buildable pattern can be constructed ... by dvgrn on Wednesday November 30, 2022 @07:54AM (#33799976)
If you want to see what these 21-bit still lifes look like, their glider construction recipes are all stored online, on Catagolue (no, that's not a misspelling):

https://catagolue.appspot.com/census/b3s23/synthesis-costs/x...

Re:In Game of Life any buildable pattern can be constructed ... by biggiemac42 on Wednesday November 30, 2022 @05:13AM (#33798911)
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.
Re:In Game of Life any buildable pattern can be constructed ... by JKCalhoun on Wednesday November 30, 2022 @10:06AM (#33801716)
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?

Re:In Game of Life any buildable pattern can be constructed ... by OscarCunningham on Wednesday November 30, 2022 @10:14AM (#33801820)
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.