Conway's Life: Garden of Eden Pattern

For discussion of other cellular automata.
Post Reply
Karapet
Posts: 4
Joined: February 8th, 2013, 10:52 am

Conway's Life: Garden of Eden Pattern

Post by Karapet » February 18th, 2013, 10:46 am

In Conway's Game of Life, a Garden of Eden pattern is defined to be a pattern that cannot
arise from a previous pattern. If it exists at all, it must be as part of the starting state.
How to prove, that there are no 2x2 and 3x3 garden of eden patterns (with one or two live squares)
does not exist(without using computer)?
Thanks much in advance!!!

Kasuha
Posts: 55
Joined: November 1st, 2012, 11:39 am

Re: Conway's Life: Garden of Eden Pattern

Post by Kasuha » February 18th, 2013, 11:49 am

I don't see a point in not using a computer but it definitely is possible to enumerate all possible 2x2 and 3x3 fields with one or two live cells and then manually find predecessor for each of them.

User avatar
Tropylium
Posts: 406
Joined: May 31st, 2011, 7:12 pm
Location: Finland

Re: Conway's Life: Garden of Eden Pattern

Post by Tropylium » February 19th, 2013, 3:35 pm

It really does not seem there would exist a proof by anything else than exhaustion, but this isn't too hard to do by hand. Like this kind of a list takes maybe 20 minutes to whip up… less if you start with a pre-generated list of all the 3×3 patterns modulo rotation/reflection:

Code: Select all

x = 144, y = 65, rule = B3S23
o$bo$2bo9$bo$obo8$11bo$bo$obo7bobo2$bo9bo6$12bo7bo$bo9bo9bo$b2o8b2o9bo
$23bo7$21bo28bo12bo7bo28bo9bo$bo20bo18bo10bo9bo19b2o8bo$b2o7b3o8bo9b3o
8b2o7bo9bo9b2o8bo9bobo7b2o8b2o$2bo10bo7b2o8bo9bo9b2o8b2o19b2o7bo$71bo
20bo8bo11bo6$22bo69b2o$12bo19bo28b2o8bo9bo19bobo7bo$5o6b2o8b3o6b2ob2o
5b3obo6b3o8bo8b2obo6b4o6b2o8b3o7b2o$12bo9bo9bo10bo8bo9bo10bo18bo9bo9b
2o$13bo48bo18bo11bo6$80bo$bo22bo9bo6bo9bo9b2o19bo8bo9bo9bo9b2o8b2o8b2o
$obo7b3o7b3o7b3o7bobo9b2o8bo8b3o6bo2b2o6b3o8b2o6bob2o6bo2bo7b3o7b3o$2b
2o8b2o9bo9bo9bo8bo9bo8bo2bo5bobo9bo9b2o8b2o9bo8bo$23bo18bo17bo3bo35bo
21bo19bo!
Can't be bothered to do the 3×3 cases with 5 to 2 cells though.

(I additionally tried squeezing everything to 6 cells or less. Mostly possible but apparently not for the 9th shape in the lower row.)

From 4×4 up I imagine GoEs are searched by attempting to combine some of the 4×4 blocks with very few parents though?

OHAD
Posts: 16
Joined: March 24th, 2013, 12:43 pm

Re: Conway's Life: Garden of Eden Pattern

Post by OHAD » April 17th, 2013, 9:07 am

I'll ask the opposite question- How can you proof for specific patterns that they ARE Gardens Of Eden?
I mean, a small Garden Of Eden might actually be the next generation of a dissolving pattern with a population of 10^52, and we'll never get close to discover the parent, but even then, it won't count as a GOE.
Just a 13-years old kid.

Kasuha
Posts: 55
Joined: November 1st, 2012, 11:39 am

Re: Conway's Life: Garden of Eden Pattern

Post by Kasuha » April 17th, 2013, 4:51 pm

OHAD wrote:I'll ask the opposite question- How can you proof for specific patterns that they ARE Gardens Of Eden?
I mean, a small Garden Of Eden might actually be the next generation of a dissolving pattern with a population of 10^52, and we'll never get close to discover the parent, but even then, it won't count as a GOE.
Each cell is a result of interaction of 9 cells in previous generation. So all you really need is to search for a predecessor which is 1 cell bigger in each direction than the claimed GoE and each cell behind that limit is set to "don't care". If no predecessor exists in that area then the pattern is GoE.

User avatar
Tropylium
Posts: 406
Joined: May 31st, 2011, 7:12 pm
Location: Finland

Re: Conway's Life: Garden of Eden Pattern

Post by Tropylium » April 27th, 2013, 4:30 pm

Kasuha wrote:
OHAD wrote:I'll ask the opposite question- How can you proof for specific patterns that they ARE Gardens Of Eden?
I mean, a small Garden Of Eden might actually be the next generation of a dissolving pattern with a population of 10^52, and we'll never get close to discover the parent, but even then, it won't count as a GOE.
Each cell is a result of interaction of 9 cells in previous generation. So all you really need is to search for a predecessor which is 1 cell bigger in each direction than the claimed GoE and each cell behind that limit is set to "don't care". If no predecessor exists in that area then the pattern is GoE.
Actually, this argument only shows that it's simple to show that a pattern is an orphan. It does not rule out the existence of GoEs that do not contain orphans… Such a pattern would be one for which a "local parent" can be found, but the edges of every parent would leave behind some junk or sparks aside from the pattern itself.

Since Life comes with D5 thru D8 though, this idea is not difficult to work around: an alleged orphanless GoE's "local parent" could be swamped with surrounding live cells, which could be then framed in this kind of a fashion:

Code: Select all

x = 16, y = 9, rule = B3/S23
bob2ob2ob2o3bo$2b11o$b13o$b13o$2b13o$b14o$b13o$2b2ob2o3b2o3bo$o7bo!
Orphanless GoEs can definitely occur in other CA, though. A single cell in any B1 rule is a (near-trivial) example…

User avatar
calcyman
Posts: 2278
Joined: June 1st, 2009, 4:32 pm

Re: Conway's Life: Garden of Eden Pattern

Post by calcyman » May 3rd, 2013, 1:49 pm

Allowing infinite subsets of Z^2 as patterns, it is easy by compactness to show that no orphanless GoEs exist.
What do you do with ill crystallographers? Take them to the mono-clinic!

Post Reply