Okay, so having read Kari's Cellular Automata Notes I can give a full proof: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: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.

- 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

- 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.

So I've tried to contact Bram to see if he can shed any light on the problem.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).