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
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).