Author 
Topic: "Erik's Puzzle" (Conway's Game of Life) (Read 5397 times) 

Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #25 on: Jul 21^{st}, 2004, 11:11am » 
Quote Modify

on Jul 21^{st}, 2004, 10:02am, Aryabhatta wrote: For instance, a whole row of N live cells in 2D case does not make the whole grid alive. 
 Sorry. Bad example, but you get what I am trying to say.


IP Logged 



JocK
Uberpuzzler
Gender:
Posts: 877


Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #26 on: Jul 23^{rd}, 2004, 3:32am » 
Quote Modify

Consider a hypercube grid with coordinates x[subi] = {1, 2, .. , N}. (i = 1, 2, ... d) Start with all N^(d1) cells that satisfy x[sub1] + x[sub2] + ... = 0 mod N as live cells. In the next step all cells that satisfy x[sub1] + x[sub2] + .. = [pm]1 mod N become alive. Etc. JCK


IP Logged 
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
x^{y}  y = x^{5}  y^{4}  y^{3} = 20; x>0, y>0.



rmsgrey
Uberpuzzler
Gender:
Posts: 2846


Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #27 on: Jul 23^{rd}, 2004, 4:07am » 
Quote Modify

That doesn't quite work. For instance, in the 1D case, 0^{th} generation has cell (N) live, 1^{st} generation has cells (N1) and (N) live, but not cell (1)... A similar problem with the proof occurs with higher dimensions  while most cells worth +/k mod N come to life in the k^{th} generation, a number  in the first generation those on the boundaries  do not. At least as far as 3D, these cells do get picked up eventually, but it's not immediately obvious, and they definitely do not come to life at the time suggested by the proof offered. I suspect the pattern given is the right one, but it still needs a little work to prove it. [e]formatting[/e]

« Last Edit: Jul 23^{rd}, 2004, 4:08am by rmsgrey » 
IP Logged 



rmsgrey
Uberpuzzler
Gender:
Posts: 2846


Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #28 on: Jul 23^{rd}, 2004, 4:13am » 
Quote Modify

on Jul 21^{st}, 2004, 11:11am, Aryabhatta wrote: Sorry. Bad example, but you get what I am trying to say. 
 A 2*N checkerboard strip is enough for the N*N grid  it has N live cells, no two of which share a side, so has a livenonlive boundary of 4N, yet will never grow beyond the 2*N strip...


IP Logged 



JocK
Uberpuzzler
Gender:
Posts: 877


Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #29 on: Jul 23^{rd}, 2004, 4:42am » 
Quote Modify

on Jul 23^{rd}, 2004, 4:07am, rmsgrey wrote: I suspect the pattern given is the right one, but it still needs a little work to prove it. 
 You're right. The growth works as indicated for grids with periodic boundary conditions. To start with N^(d1) live cells that satisfy X1 + X2 + .. + Xd = 0 mod N (Xi = 1, 2, .. N) also does the job for 'dead' boundaries, but the growth towards a full live lattice is slower: first a (N1)^d hypercube is filled with live cells, and subsequently the last layers in all d directions become live. JCK


IP Logged 
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
x^{y}  y = x^{5}  y^{4}  y^{3} = 20; x>0, y>0.



JocK
Uberpuzzler
Gender:
Posts: 877


Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #30 on: Jan 19^{th}, 2005, 2:53pm » 
Quote Modify

on Mar 31^{st}, 2003, 10:37am, william wu wrote:In a strippeddown version of Conway's game of life, cells are arranged on a square grid. Each cell is either alive or dead. Live cells do not die. Dead cells become alive if two or more of their immediate neighbours are alive. 
 This 'strippeddown version of the game of life' appears to be known known as 'bootstrap percolation': http://mathworld.wolfram.com/BootstrapPercolation.html The question "what random density of life cells do you need to start with so as to reach an 'all cells life' situation?" has an interesting answer (that apparently could not be deducted from computer simulations). B.t.w.: do we consider 'Erik's puzzle' solved (in all spatial dimensions)? It is on the list of unsolved problems, but for the periodic boundary conditions commonly used in Cellular Automata research (see e.g. the animation shown on the above Mathworld page) the answer is straightforward, isn't it?


IP Logged 
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
x^{y}  y = x^{5}  y^{4}  y^{3} = 20; x>0, y>0.



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #31 on: Jan 19^{th}, 2005, 3:40pm » 
Quote Modify

on Jan 19^{th}, 2005, 2:53pm, JocK wrote: The question "what random density of life cells do you need to start with so as to reach an 'all cells life' situation?" has an interesting answer (that apparently could not be deducted from computer simulations). 
 This might not be what you are talking about, but there is a thread already: Erik's Puzzle Probability started by EigenRay in the medium forum.


IP Logged 



rmsgrey
Uberpuzzler
Gender:
Posts: 2846


Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #32 on: Jan 20^{th}, 2005, 8:20am » 
Quote Modify

on Jan 19^{th}, 2005, 2:53pm, JocK wrote:B.t.w.: do we consider 'Erik's puzzle' solved (in all spatial dimensions)? It is on the list of unsolved problems, but for the periodic boundary conditions commonly used in Cellular Automata research (see e.g. the animation shown on the above Mathworld page) the answer is straightforward, isn't it? 
 The problem we're most interested in (and the unsolved one) is the less trivial case where the boundaries never contribute live cells  for dimensions higher than 1, this is equivalent to embedding the working hypercube in a larger, otherwise empty, hypervolume.


IP Logged 



