From: "Adam P. Goucher" <apgoucher@gmx.com> Mainly to Bill Gosper: Theorem: There exists a universal constant K such that for any unbounded weakly-increasing computable function f : N --> N (such as the inverse Ackermann function), there exists an infinite-growth pattern such that the population at time t is bounded above by f(t) + K. Proof: Build a universal counter machine using a modified sliding-block memory (where the machine waits for a return signal bouncing back from the block before proceeding). Program it to successively evaluate f(n) - f(n - 1)...

--I think Goucher's proof is correct, at least if one ignores his details. The key word is "sliding block counter machine" where only a bounded number of counters are needed for turing universality; at any single step such a machine can choose a counter, increment or decrement it, change state (bounded number of states), and perform some simple tests on the counters. Now EXTENDED THEOREM: Goucher's upper bound is best possible in the sense that if f(t) were any (non-strictly) increasing function N-->N whose inverse was UNcomputably-rapidly increasing, i.e. increasing faster than any computable function [so f(t) itself increases to infinity but more slowly than any increasing computable function of t which does so] then Goucher's upper bound would become false. PROOF SKETCH: using a spiral-type enumeration, number all the cells in the CA outward from center. Using a turing machine, simulate the CA while also keeping track of the number of CA steps simulated, and the CA population. Keep going until reach t steps. This proves the population at time t is a computable function. This contradiction with the hypothesis proves the attempted Goucher-theorem-improvement is false, i.e. no such improved theorem is possible, i.e. Goucher's theorem is "best possible" in the sense claimed. QED.