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:
- check that the bounding box of the live cells plus a thickness-4 padding of dead cells in all directions is an orphan, or
- 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!