The Cook Book

Recipe for the week of March 4 - 10

Wolfram's Circle: an Isotropic CA Growth Model?

We welcome spring to the Kitchen with another chapter in our ongoing discussion of cellular automaton growth models. Recall that the basic Threshold Growth dynamics, described last summer, spread out with Polygonal Asymptotic Shapes L, whereas some of the Non-Monotone CA Growth Rules from last fall have nonconvex limiting L. Another intermediate possibility, which seems to arise in some non-monotone rules, is a convex L with smooth boundary. Ten years ago, in their paper "Two-dimensional cellular automata" J. Stat. Phys. 38 (1985), 901-946, Norman Packard and Stephen Wolfram raised the possibility that certain slowly spreading CA growth rules might produce isotropic growth, i.e., give rise to an asymptotic shape L that is a perfect Euclidean circle. In that paper they gave nearest neighbor examples that were roughly circular, but stopped short of claiming any specific model was exactly isotropic. Janko Gravner and I can construct Threshold Growth examples with fairly small range of interaction for which the deviation of L from a circle is less than 2% (in a sense to be spelled out below) even though L is in fact a polygon. We stubborn mathematicians tend to subscribe to the macabre old maxim, "Close only counts in horseshoes and hand grenades," so perhaps this kind of question is not so interesting to an engineer. But the issue of whether local parallel dynamics can sometimes overcome the anisotopy of the underlying lattice seems fundamental to our theoretical understanding of cellular automata.

So last fall Stephen Wolfram told me of a new CA rule that does a better job of making circles than any he had previously discovered. I am not at liberty to divulge the specific dynamics since he intends to feature this example in a forthcoming book. But he did sanction the use of our mixmaster CAM8 to test the isotropy conjecture every 500 updates until it filled an 8K by 8K array, the largest CA experiment we have ever performed. This week's soup shows the rule, which we call Wolfram's Circle, after 600 updates, starting from a lattice ball of 'radius' 10, and using a periodic palette of size 200 to color the occupied sites. Those with large desktops can also view Wolfram's Circle after 1,000 updates.

In order to test for a circular limit shape L, we measured the extent of the growth in the horizontal and 45 degree directions at times 500, 1000, ..., 10000 (starting from a somewhat larger lattice circle). More precisely, at each such time we computed the distance from the origin to the closest hyperplanes touching the occupied set, and normal to the horizontal and diagonal directions. The results h(t) and d(t), together with the Eccentricity = h(t)/sqrt(2)d(t), are tabulated in our Shape Data for 10,000 updates. We leave it for you to decide whether the numbers support isotropy, or whether - as for the Threshold Growth examples mentioned earlier - there is a residual anisotropy on the order of a few per cent.

Take me higher...
Introduction to the PSK PSK Search Recent Additions CA Archive CA Links Feedback Appreciated !