Conway's Life: Garden of Eden Pattern

[Karapet]

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]

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.

[Tropylium]

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]

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.

[Kasuha]

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.

[Tropylium]

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…

[calcyman]

Allowing infinite subsets of Z^2 as patterns, it is easy by compactness to show that no orphanless GoEs exist.