3 ms·
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.
by 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 agoah yes, you're right. thanks...
- camccann 17y agoActually, 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).