ConwayLife.com

Macbi wrote:[...] for every GoE (considered as an infinite pattern where all cells are either on or off) we can find a finite subset of the cells which is an orphan.

[...]

But I've run into this sort of argument before. I bet it boils down to the following:

• Suppose we had a pattern containing no orphans
• Then we can look at a 1 by 1 box. It's not an orphan, so there must be some predecessor that works at least inside that box
• Then expand it to a 3 by 3 box. It's not an orphan, so there must be some predecessor that works at least inside that box. This predecessor must be consistent with one of the predecessors for the 1 by 1 box, because we can just restrict it
• Carry on in this way, continually expanding to larger boxes
• Stitch together all these consistent partial predecessors to form an actual predecessor for the whole pattern
• So if a pattern contains no orphans then it has a predecessor
• So every GoE contains an orphan

The difficult bit it the precise details of the "stitching together" process. It's probably not too hard to work out the details by hand, but if you're a mathematician it seems more elegant to use a "compactness" argument like Kari does above.

Okay, so having read Kari's Cellular Automata Notes I can give a full proof:

• Suppose we have a pattern containing no orphans
• Let P_1, P_2, ... be a list of patterns (assignments of alive or dead to every cell in the infinite grid) such that the succesor of P_n agrees with the pattern at least on the n by n square centred on the origin
• Let c_1, c_2, ... be a labelling of all the cells in the grid, spiralling outwards from the origin
• Consider the assignment to c_1 in each of the patterns P_1, P_2, ... . We pick an assignment of c_1 that agrees with infinitely many of the P_n, and we henceforth restrict our attention to the P_n that agree with this assignment
• Now pick an assignment to c_2 that agrees with infinitely many of the remaining P_n, and restrict the list of P_n again
• Continuing in this way, create an assignment for every c_m
• Then the pattern thus formed is a predecessor for our original pattern, because the value of any cell is determined by only finitely many of the c_m, and these agree with the P_n for arbitrarily large values of n, in particular for n large enough that the n by n box contains the given cell.

Also on this page I found the following

Bram Cohen claims that if a pattern has an orphan predecessor in an n+2 by m+2 rectangle, then you can add on ON cells to the orphan predecessor to make a proper predecessor (i.e., one that turns into the wanted pattern with no extra on cells outside the bounding box of the wanted pattern).

So I've tried to contact Bram to see if he can shed any light on the problem.

The problem of deciding whether a given finite-population pattern is a GoE has been rattling about in my brain for the last couple of years. So when I saw a mathoverflow question asking for "Decision problems for which it is unknown whether they are decidable" I quickly posted it as an example of such. This lead to Ville Salo and Ilkka Törmä learning about the problem, and they've managed to solve it!

Their paper "Gardens of Eden in the Game of Life" shows that it is decidable whether or not a given finite-population pattern is a GoE:

Ville Salo and Ilkka Törmä wrote:We prove that in the Game of Life, if the thickness-four zero-padding of a rectangular pattern is not an orphan, then the corresponding finite-support configuration is not a Garden of Eden, and that the preimage of every finite-support configuration has dense semilinear configurations. In particular finite-support Gardens of Eden are in co-NP.

Interestingly their paper doesn't proceed in the manner discussed in this thread, by proving the lemma that every finite-population non-GoE has a finite-population predecessor. Indeed this lemma remains an open problem. Instead they show that every finite-population non-GoE has a semilinear predecessor (meaning one which is eventually periodic in each direction). Since the semilinear patterns may be algorithmically enumerated we are guaranteed to eventually find a predecessor if one exists.

This lead to Ville Salo and Ilkka Törmä learning about the problem, and they've managed to solve it!

I'm one of the authors (and writing on behalf of Ville Salo as well). In our preprint we give two different algorithms for deciding if a finite-population configuration is GoE:

1. check that the bounding box of the live cells plus a thickness-4 padding of dead cells in all directions is an orphan, or
2. check that it doesn't have a predecessor that is eventually periodic in all directions (we give bounds for the period and the length of the non-periodic part so this can theoretically be done in finite time).

The first algorithm is more "practical" because a thickness-4 padding is somewhat reasonable, but the second gives a concrete predecessor if one exists.

As stated, we don't know whether all finite-population non-GoE configurations have finite-population predecessors. However, we have a possible strategy of showing that this is not the case: find a finite-population non-GoE configuration x that forces the occurrence of a pattern we call P_0 in every predecessor outside the bounding box of live cells of x (or just on the border, with one row of cells being in the box). Then it would force the predecessors to have an infinite number of live cells. This might be doable with SAT solvers but we are not that well versed in them.

If you have questions about the paper, please ask and I'll try to answer!