Intro Soup Recipe Shelf Sink Chef
Take me higher...

Lagniappe #7

Totalistic Growth Rules with Moore Neighborhood

Collected here are 5 images of crystal growth based on simple cellular automaton rules with 8 nearest neighbors : N, S, E, W, NE, SE, NW, SW. See Two-State Range 1 Automata for Java versions of some of these same Moore neighborhood dynamics. Totalistic means that state transitions depend only on the population count of the neighborhood. Our images paint the cells added during each update with a new color from a gradient palette. First, for the title postcard above, start with only the origin occupied, then repeatedly add to the crystal any site with exactly 1 of its 8 neighbors previously occupied. Click on the thumbnail image to see the crystal after 219 updates. in a festive time-trace coloration. We have chosen 219 because it is the closest integer to 6/7 of 256. It turns out that at times which are 6/7 of successive powers of 2 the crystal's shape converges to a limit with self-similar corners and boundary of infinite length. As a puzzle, see if you can figure out the asymptotic density of illuminated cells when the crystal is very large.

Change the birth rule from exactly 1 to exactly 2 occupied neighbors, and start from a horizontal dyad, to obtain a roughly diamond-shaped crystal with elaborate pseduo-random detail. Whether, after rescaling, the growth attains the asymptotic shape of an exact diamond is a delicate question in the same spirit as those raised by our discussion of shapes a couple of years ago. We suspect the answer is yes.

About the most exotic CA growth model we know is Hickerson's Amoeba; see the Range 1 Automata applet for its rule and a short simulation. Here is a crystal after thousands of updates started from a 2 x 59 horizontal strip with one corner removed. Another rendering of the same crystal is amoeba.gif. The intricate fossil-like patterns are the result of a wildly unpredictable ebb and flow of boundary layers. One can actually check that the dimple patterns along the edges emulate various one-dimensional CA rules for long periods of time. But it is still an open question whether there is any initial seed from which this model grows without bound.

Quite remarkably, the Amoeba dies away completely when started from any square seed with odd side length, no matter how large. Experiment 8 of the Range 1 Automata applet simulates this collapse from a relatively small square. Here we show a much larger one; another rendering of the same trajectory is jhilife.gif. In these images the different colors represent successive times when new 0's arise. Even more amazing is Dean Hickerson's formula for the time until an n by n occupied square disappears, n odd. It is exactly

6n - 10 - 4A + 2B - ((n - 1)/2 mod 2),

where, in the binary representation of n, A is the number of 1's and B is the number of pairs of adjacent 1's.

Finally, an interesting critical growth model called Night and Day. Discovered by Nathan Thompson, this symmetric rule dictates a flip if 3,6,7 or 8 of its neighbors disagree. From disordered initial states the system evolves like Majority Vote, but with highly nonlinear interface dynamics. Here is a graphic showing the level sets of a realization which converges to all 1's. Can you detect hints of motion by mean curvature despite the increased complexity?
Take me higher...
Intro Soup Recipe Shelf Sink Chef