wu :: forums
« wu :: forums - "Erik's Puzzle" (Conway's Game of Life) »

Welcome, Guest. Please Login or Register.
Jan 24th, 2022, 11:20am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: Eigenray, Icarus, ThudnBlunder, SMQ, towr, Grimbal, william wu)
   "Erik's Puzzle" (Conway's Game of Life)
« Previous topic | Next topic »
Pages: 1 2  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: "Erik's Puzzle" (Conway's Game of Life)  (Read 5397 times)
Aryabhatta
Uberpuzzler
*****






   


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

on Jul 21st, 2004, 10:02am, Aryabhatta wrote:

 
 
  For instance, a whole row of N live cells in 2-D 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: male
Posts: 877
Re: "Erik's Puzzle" (Conway's Game of Life)  
« Reply #26 on: Jul 23rd, 2004, 3:32am »
Quote Quote Modify Modify

Consider a hypercube grid with coordinates x[subi] = {1, 2, .. , N}. (i = 1, 2, ... d)
 
Start with all N^(d-1) 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.
 
JCoolCK
IP Logged

solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.

xy - y = x5 - y4 - y3 = 20; x>0, y>0.
rmsgrey
Uberpuzzler
*****





134688278 134688278   rmsgrey   rmsgrey


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

That doesn't quite work. For instance, in the 1-D case, 0th generation has cell (N) live, 1st generation has cells (N-1) 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 kth 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 23rd, 2004, 4:08am by rmsgrey » IP Logged
rmsgrey
Uberpuzzler
*****





134688278 134688278   rmsgrey   rmsgrey


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

on Jul 21st, 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 live-nonlive boundary of 4N, yet will never grow beyond the 2*N strip...
IP Logged
JocK
Uberpuzzler
*****






   


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

on Jul 23rd, 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^(d-1) 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 (N-1)^d hypercube is filled with live cells, and subsequently the last layers in all d directions become live.
 
JCoolCK
IP Logged

solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.

xy - y = x5 - y4 - y3 = 20; x>0, y>0.
JocK
Uberpuzzler
*****






   


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

on Mar 31st, 2003, 10:37am, william wu wrote:
In a stripped-down 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 'stripped-down 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.

xy - y = x5 - y4 - y3 = 20; x>0, y>0.
Aryabhatta
Uberpuzzler
*****






   


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

on Jan 19th, 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
*****





134688278 134688278   rmsgrey   rmsgrey


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

on Jan 19th, 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
Pages: 1 2  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board