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), and emit a glider if it is non-zero. Now pass the output into three successive pulse-dividers. Then the population at time t is bounded as follows: pop(t) <= K + 5 floor(f(n) / 8) <= K + f(n) <= K + f(t) where n is the number of complete cycles that have occurred thus far. Sincerely, Adam P. Goucher
Sent: Wednesday, April 22, 2015 at 12:36 AM From: "Bill Gosper" <billgosper@gmail.com> To: math-fun@mailman.xmission.com Subject: [math-fun] CA minimum growth
Everybody knows that the area and population growth of a bounded 2D cellular automaton pattern is limited to ~ time^2, but it never occurred to me that there is a theoretically minimal positive (diameter) growth rate ~ sqrt(log t), achieved in Life by Adam Goucher's [Golly Help] [Online Archives] [Very Large Patterns] [O(sqrt(log(t)))], which counts in binary with an infinite triangular array of "boats". Question: Is sqrt(log(t)) also the theoretically minimum growth of population? --rwg _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun