3 ms·

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.

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.

camccann 17y ago
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.
- andrewcooke 17y ago
  ah yes, you're right. thanks...
  - camccann 17y ago
    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 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).

camccann 17y ago

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.

andrewcooke 17y ago
ah yes, you're right. thanks...
- camccann 17y ago
  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 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).