I ended up in a deadlock. No new mushrooms are growing and the existing mushrooms are in a pattern where they won't die. Does this mean I won or lost? ;)
this made me wonder whether there's some function of the number of cells for which, if a population stays alive for that number of cycles, it will live forever.
for example, for a 10x10 grid, maybe any pattern that has life after 100 cycles will always have life.
i guess this might be covered in "a new kind of science" - i haven't read that. any who has care to comment? thanks.
The function you're looking for would be a variation of the Busy Beaver function, I think. On an infinite grid, the question reduces to the Halting Problem.
Actually, my apologies for the overly brief comment earlier, I was on lunch and typing on a smartphone.
I suppose you understood my point, but I'll elaborate for posterity: Conway's Life is Turing complete, with the conceptually unbounded grid standing in for the infinite tape of a Turing machine. As illustration, here's a page that implements a literal Turing machine using Life patterns: http://rendell-attic.org/gol/tm.htm
Starting from an empty tape, the number of states in the Turing machine must obviously be proportional to the number of live cells needed; updates to the state of the grid are equivalent to running time for the TM; and the output produced by the machine must be proportional to the population of live cells.
From this, we can (in a non-rigorous, hand-wavy sort of way) conclude that asking for an upper bound on the number of cycles to decide if any grid of a given finite size will be populated or barren is very likely equivalent to asking for an upper bound on the running time needed to decide if a Turing Machine of a given finite number of states will halt. This isn't actually the Busy Beaver function, but is closely related.
Thus concludes my proof by enthusiastic hand-waving (if there isn't a fancy Latin term for that, there should be).
Comments
I ended up in a deadlock. No new mushrooms are growing and the existing mushrooms are in a pattern where they won't die. Does this mean I won or lost? ;)
It sounds to me like you're not familiar with Conway's Life.
http://en.wikipedia.org/wiki/Conways_Game_of_Life
this made me wonder whether there's some function of the number of cells for which, if a population stays alive for that number of cycles, it will live forever.
for example, for a 10x10 grid, maybe any pattern that has life after 100 cycles will always have life.
i guess this might be covered in "a new kind of science" - i haven't read that. any who has care to comment? thanks.
The function you're looking for would be a variation of the Busy Beaver function, I think. On an infinite grid, the question reduces to the Halting Problem.
ah yes, you're right. thanks...
Actually, my apologies for the overly brief comment earlier, I was on lunch and typing on a smartphone.
I suppose you understood my point, but I'll elaborate for posterity: Conway's Life is Turing complete, with the conceptually unbounded grid standing in for the infinite tape of a Turing machine. As illustration, here's a page that implements a literal Turing machine using Life patterns: http://rendell-attic.org/gol/tm.htm
Starting from an empty tape, the number of states in the Turing machine must obviously be proportional to the number of live cells needed; updates to the state of the grid are equivalent to running time for the TM; and the output produced by the machine must be proportional to the population of live cells.
From this, we can (in a non-rigorous, hand-wavy sort of way) conclude that asking for an upper bound on the number of cycles to decide if any grid of a given finite size will be populated or barren is very likely equivalent to asking for an upper bound on the running time needed to decide if a Turing Machine of a given finite number of states will halt. This isn't actually the Busy Beaver function, but is closely related.
Thus concludes my proof by enthusiastic hand-waving (if there isn't a fancy Latin term for that, there should be).
Another cool one to try the spinner 3 in a row
I am a complete sucker for all things Life. Awesome!
Cute visualization!