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