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
On Tue, Apr 21, 2015 at 4:36 PM, Bill Gosper <billgosper@gmail.com> wrote:
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),
... which follows from a counting argument. Nice! (Obviously you mean minimum positive growth rate; any still life has growth rate zero, and infinitely many patterns shrink to nothing.) -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
This has bearing on physics: surprisingly, the entropy of a black hole scales with the _surface area_ rather than the volume. On Tue, Apr 21, 2015 at 5:08 PM, Mike Stay <metaweta@gmail.com> wrote:
On Tue, Apr 21, 2015 at 4:36 PM, Bill Gosper <billgosper@gmail.com> wrote:
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),
... which follows from a counting argument. Nice! (Obviously you mean minimum positive growth rate; any still life has growth rate zero, and infinitely many patterns shrink to nothing.) -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.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), 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
But won't maintaining n mess things up? On Apr 22, 2015 12:22 AM, "Adam P. Goucher" <apgoucher@gmx.com> wrote:
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I don't understand. Arbitrarily large integers can be stored in a register of bounded population: http://www.radicaleye.com/lifepage/patterns/sbm/sbm.html
Sent: Wednesday, April 22, 2015 at 8:57 AM From: "Tom Rokicki" <rokicki@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] CA minimum growth
But won't maintaining n mess things up? On Apr 22, 2015 12:22 AM, "Adam P. Goucher" <apgoucher@gmx.com> wrote:
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (4)
-
Adam P. Goucher -
Bill Gosper -
Mike Stay -
Tom Rokicki