Author |
Topic: "Erik's Puzzle" (Conway's Game of Life) (Read 5619 times) |
|
Aryabhatta
Uberpuzzler
Gender: 
Posts: 1321
|
 |
Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #25 on: Jul 21st, 2004, 11:11am » |
 Quote  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:
Posts: 877
|
|
Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #26 on: Jul 23rd, 2004, 3:32am » |
Quote 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.
J CK
|
|
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
    
Gender:
Posts: 2872
|
|
Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #27 on: Jul 23rd, 2004, 4:07am » |
Quote 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
Gender:
Posts: 2872
|
|
Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #28 on: Jul 23rd, 2004, 4:13am » |
Quote 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:
Posts: 877
|
|
Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #29 on: Jul 23rd, 2004, 4:42am » |
Quote 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.
JCK
|
|
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:
Posts: 877
|
|
Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #30 on: Jan 19th, 2005, 2:53pm » |
Quote 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:
Posts: 1321
|
|
Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #31 on: Jan 19th, 2005, 3:40pm » |
Quote 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
Gender:
Posts: 2872
|
|
Re: "Erik's Puzzle" (Conway's Game of Life)
« Reply #32 on: Jan 20th, 2005, 8:20am » |
Quote 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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print