Gardens of Eden

[mtve]

Hello everybody!

There are some interesting things found while searching for more Gardens of Eden, so new thread is started to welcome your opinions and ideas.

First, random GoEs.

Surprising fact: random pattern of size 20x20 with 50% on-cells is GoE with probability around 1/4. But 72% on-cells will raise that probability to more than 3/4, and the curve of GoE chance by on-cells density is very interesting. Nice 4D map needs to be drawn with GoE probabilities on NxM pattern with L% on-cells.

It's a bit sad that most of GoL patterns are GoEs (i.e. any big pattern with balanced density). Luckily random GoEs are much bigger than small-sized records. It feels like there are some internal invisible forces that keep different parts of a pattern like springs until it crystallizes to the GoE, and in random GoE these springs are hanging loosely separated by spaces while in the smallest records these springs are packed tightly. The key to such forces could open the door to new records.

Second, opposite of random, periodic GoEs.

There are a few 4x4 patterns, for example:

Code: Select all

....
..X.
.X.X
XXX.

that repeated 6x6 times become 24x24 GoE.

Smaller patterns, other tessellations, what do you think?

[Gamedziner]

You need to post the code like this:

Code: Select all

....$
..X.$
.X.X$
XXX.!

The important part is the "$".

Actually, this is 4x3:

Code: Select all

..X.$
.X.X$
XXX.!

[mtve]

Code: Select all

..X.$
.X.X$
XXX.!

Assuming you've repeated this 6 times horizontally and 7 times vertically, yes, it's also periodic GoE. Nice catch!

[mtve]

Notes on periodic GoEs.

3x3: It seems no 3x3 tile can become a GoE.

3x4: Indeed possible, as shown by Gamedziner. Non-squares to be investigated: 2x4, 2x5, 2x6, 3x4, 2x7 and 3x5.

4x4: There are 805 possible 4x4 tiles (sequence https://oeis.org/A255016, see also http://arxiv.org/abs/1502.03792v1).
306 of them are making GoE when repeated at least 6x6 times.
250 of them are making GoE when repeated at least 5x5 times.
125 of them are making GoE when repeated at least 4x4 times, which is minimal possible repetition of 4x4 square tile.

Interesting are unique 5-cells ("brick wall", very low density! requires 6x6 repeat):

Code: Select all

...X$
..X.$
.X..$
X.X.!

and unique 14-cells (no connected off-cells! requires 4x4 repeat):

Code: Select all

XXXX$
.XXX$
XX.X$
XXXX!

So if you are caught by supernatural creatures and asked to draw a GoE, you can do it easily now.
Just remember the last one and repeat it 4x4 times to 16x16 pattern.

5x5, 6x6: Next.

[Scorbie]

Hmm! I don't have much to say, but these are interesting and great work

Surprising fact: random pattern of size 20x20 with 50% on-cells is GoE with probability around 1/4. But 72% on-cells will raise that probability to more than 3/4, and the curve of GoE chance by on-cells density is very interesting.

And this is very intersting to know!

Are you working on these with that algorithm you came out with a while before?

[mtve]

Hmm! I don't have much to say, but these are interesting and great work

Thank you very much, really nice to hear this!

Are you working on these with that algorithm you came out with a while before?

Basically I just run a SAT solver (cryptominisat is great) to search a parent for random pattern, and it's a GoE if configuration is UNSAT.

Here is small script to make a cnf file from a pattern: http://frox25.no-ip.org/~mtve/tmp/gol_cnf.pl (gol2_cnf.pl for grand-parent).

I guess I need to put all my tools to github, it just requires big cleanup and documentation. Ideas came too chaotic, and quick and dirty hacks to try new hypotheses are too messy.

[mtve]

There are new Gardens of Eden found by Steven Eker, now only with 89 cells!
Information is here http://wwwhomes.uni-bielefeld.de/achim/orphan_10th.html

And also I've found GoE-4G (no grand-grand-grand-parent pattern), http://frox25.no-ip.org/~mtve/wiki/GardenOfEden4G.html

Unfortunately I can't put it in the wiki now, would administrators or any trusted user please update "Garden of Eden" page? Many thanks in advance.

[Saka]

Some questions:
-How do you find these?
-How do you check if it is a GoE?

[mtve]

Some questions:
-How do you find these?

I've found Eker's new patterns by routine checking of Achim Flammenkamp's page. I'm not aware of any other sources, if you know Eker's blog or some other place where his results get published - it would be really great. I have no idea on how he finds his patterns, again explanation will be highly appreciated.

What about my 4G, I've put some of my tools at https://github.com/mtve/goe , and the technique was the same as for http://www.conwaylife.com/wiki/Grandfather_problem

-How do you check if it is a GoE?

I construct SAT instance for three generations and it has solutions, while four generations has not. You may find constructors in my tools.

[Sokwe]

I'm not aware of any other sources, if you know Eker's blog or some other place where his results get published - it would be really great. I have no idea on how he finds his patterns, again explanation will be highly appreciated.

I don't think he has made any of his work public. The best way to get that information is probably to email him directly. You might be able to contact him through his work email at SRI International. His information can be found here.

[mtve]

I don't think he has made any of his work public. The best way to get that information is probably to email him directly. You might be able to contact him through his work email at SRI International. His information can be found here.

Thanks, I saw his page, I don't get enough courage to bother him, yet

[dvgrn]

Unfortunately I can't put it in the wiki now, would administrators or any trusted user please update "Garden of Eden" page? Many thanks in advance.

Okay, I've made a start -- added the 89-cell GoE to the records table.

Looks to me like Garden of Eden 7, 8, 9, and 10 pages should probably be added, to get the GoE category page up to date. There's a bit of a naming problem, in that there are actually two separate Steven Eker record-breakers on the Garden of Eden 9th page. Might have to arbitrarily rename the second one to "Garden of Eden 8x12", I guess.

[BlinkerSpawn]

The table on the bottom of Achim's pages notes the minimal density of on-cells as 0.3203 but we have the 0.2 periodic tile noted by mtve above.

[mtve]

Okay, I've made a start -- added the 89-cell GoE to the records table.

Almost perfect! The only thing is second line from bottom is a honorable mention but not a record (red), since the third line from bottom had height 5 before that.

The table on the bottom of Achim's pages notes the minimal density of on-cells as 0.3203 but we have the 0.2 periodic tile noted by mtve above.

I guess density in this table is interesting only for compact GoEs, because it's possible to construct arbitrary sized pattern with any density. (Edit: Err, 0.2? Was it 0.3125?) (More edit: apparently this paragraph is wrong, there are lower and upper limits on GoE density)

P.S. Is that only me, or the site is kinda slow recently?

[Sokwe]

second line from bottom is a honorable mention but not a record (red), since the third line from bottom had height 5 before that.

They share the record (it doesn't matter which was found first). Notice that there are also two patterns that share the record for fewest on cells (45).

I guess density in this table is interesting only for compact GoEs, because it's possible to construct arbitrary sized pattern with any density.

The density is the entry in the "on-cells" column divided by the entry in the "orphan" column. The orphan is the finite collection of cells that need to be set in the pattern. This orphan should be minimal in the sense that removing any single cell creates a pattern that is not an orphan. If we restrict to minimal orphans, I think this should give a well-defined density. I'm not sure if this property has been checked for any of the orphans listed on that page.

By the way, if you want to edit the wiki you should ask Nathanial, as he is the only one with the ability to edit user rights.

[dvgrn]

Notes on periodic GoEs.

3x3: It seems no 3x3 tile can become a GoE.

3x4: Indeed possible, as shown by Gamedziner. Non-squares to be investigated: 2x4, 2x5, 2x6, 3x4, 2x7 and 3x5...

Thanks to recent Garden of Eden activity, I finally came up with the last five LifeWiki Did-You-Knows, to hit my arbitrary interim goal of 75. Now working on my original goal of 100...!

Yesterday I put in a #76 based on periodic GoE tiles. But when I thought about it some more, I decided I didn't really believe the first line above, as it's written. Are there any caveats, like "with up to 6x6 copies of the tile"?

If no 3x3 tile can become a GoE, no matter how many times it's repeated, it almost seems like in the limit there would have to be a 3x3 agar predecessor of every 3x3-tiled infinite agar. That's not quite true, because theoretically you could have a 6x6 or 9x12 or whatever sized predecessor whose child is a perfectly tiled 3x3 agar. But I'm not sure that will really save the "almost-infinite" case... (?)

It also occurs to me to be curious about the 2x2 case. In particular, is there really a predecessor for a tiling of

Code: Select all

x = 2, y = 2, rule = B3/S23
o$bo!
[[ THUMBNAIL VIEWONLY ]]

no matter how big the checkerboard gets?

[Kazyan]

It also occurs to me to be curious about the 2x2 case. In particular, is there really a predecessor for a tiling of

Code: Select all

x = 2, y = 2, rule = B3/S23
o$bo!
[[ THUMBNAIL VIEWONLY ]]

no matter how big the checkerboard gets?

Here's a periodic parent that solves that case:

Code: Select all

x = 19, y = 19, rule = B3/S23
3bo3bo3bo3bo$bo3bo3bo3bo3bo$3bo3bo3bo3bo$ob3ob3ob3ob3obo$3bo3bo3bo3bo$
bo3bo3bo3bo3bo$3bo3bo3bo3bo$ob3ob3ob3ob3obo$3bo3bo3bo3bo$bo3bo3bo3bo3b
o$3bo3bo3bo3bo$ob3ob3ob3ob3obo$3bo3bo3bo3bo$bo3bo3bo3bo3bo$3bo3bo3bo3b
o$ob3ob3ob3ob3obo$3bo3bo3bo3bo$bo3bo3bo3bo3bo$3bo3bo3bo3bo!

[dvgrn]

Here's a periodic parent that solves that case...

Huh, nice. So probably there's a similar periodic trick for all the 3x3 cases -- there really aren't very many, after all -- but not for some 4x3 and 4x4 cases.

2x3 is not mentioned in the list of "non-squares to be investigated", but I suppose it's not too likely that 2x3 would allow a GoE where 3x3 doesn't. (?)

[mtve]

They share the record (it doesn't matter which was found first).

It's perfect then!

If no 3x3 tile can become a GoE, no matter how many times it's repeated, it almost seems like in the limit there would have to be a 3x3 agar predecessor of every 3x3-tiled infinite agar.

I remember I've drawn graphs of convolutions of repeated (toroid) patterns, and there were cycles. It seems I've deleted my notes but it could be reproduced.

2x3 is not mentioned in the list of "non-squares to be investigated", but I suppose it's not too likely that 2x3 would allow a GoE where 3x3 doesn't.

Just checked, nope.

Many thanks to all of you for keeping this excellent wiki!

[mtve]

A bit offtopic because not exactly about GoL, but while trying to understand why GoL is so special from other CAs, I've made a search for random GoEs for Life-likes whose Born and Stay rules are sequential, and there are the tables of minimal and maximal bounds of side sizes of squares where GoEs can be found:

http://frox25.no-ip.org/~mtve/tmp/ll_goe_min.png
http://frox25.no-ip.org/~mtve/tmp/ll_goe_max.png

It casts a little light on GoL itself, the only curious thing from those tables is rule B34/S456 with abnormally big size of GoE otherwise seemed totally uninteresting. Hope it will provoke some conclusions.