- A community for Conway's Game of Life and related cellular automata
Home  •  LifeWiki  •  Forums  •  Download Golly

orphan pattern / garden of eden

For discussion of specific patterns or specific families of patterns, both newly-discovered and well-known.

Re: orphan pattern / garden of eden

Postby Macbi » October 9th, 2017, 7:29 am

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.
User avatar
Posts: 575
Joined: March 29th, 2009, 4:58 am


Return to Patterns

Who is online

Users browsing this forum: Hunting, mniemiec, wildmyron and 3 guests