Simple Initial States

Figure 2 shows the ``growth'' of a pattern from a ``seed'' consisting of a single site with value 1 (surrounded by value 0 sites) according to each of the 32 possible (legal) elementary cellular automaton rules. The evolution is shown until a particular configuration appears for the second time (a ``cycle'' is detected) or for at most 20 time steps. The patterns generated by all rules are seen to fall into a few classes. In one class, the initial 1 is either immediately erased (as by rule 0) or maintained unchanged forever (rule 4). A second class of rules (exemplified by 50 or 122) copy the initial 1 to generate a uniform structure analogous to a perfect crystal. Rules such as 18, 22 and 90 form a third class of ``complex'' rules which generate complicated patterns.

[ Figure 2 ] Growth of patterns from simple seeds according to each of the 32 possible legal elementary cellular automaton rules. Configurations at successive time steps are shown on successive lines. Sites with value 1 are represented by stars, and those with value 0 by blanks. The evolution is shown until a particular configuration appears for the second time, or for at most 20 time steps.

Figure 3 shows two constructions for the pattern generated by rule 90. Since this rule takes each site to be the sum of the previous values of its neighbours modulo two, the pattern it generates is simply Pascal's triangle modulo two (or the binomial coefficients in the expansion of the generating function modulo two). (Rule 90 may also be interpreted as generating ``stunted'' binary trees, in which two diagonal branches grow from each nonzero site at each time step, but are inhibited if they would collide.) The final pattern of nonzero sites is obtained as the limit of the recursive geometrical construction shown in fig. 3. This pattern is seen to be ``self-similar'' or ``scale invariant'', in that views with different ``magnifications'' (but the same ``resolution'') are indistinguishable. Scale invariance is to be expected, since the cellular automaton defines no intrinsic scale (except the size of a single site) in the large time limit.

[ Figure 3 ] Algebraic and geometrical constructions for the pattern generated by evolution according to the modulo two rule 90 from a ``seed'' consisting of a single nonzero site.

The pattern shown in fig. 3 contains many congruent (inverted) triangles with base lengths of sites. At large times, the number of triangles of size is given by so that . The ``fractal'' dimension [9] of the pattern is thus . A uniform pattern, as generated by rule 50, has a fractal dimension two, while a line, as generated by rule 4, has fractal dimension one.

Figure 2 shows that all ``complex'' cellular automaton rules yield asymptotically self-similar patterns. All give the same fractal dimension except for rule 150 which gives a fractal dimension where is the ``golden ratio''.

Patterns generated by cellular automaton evolution from ``seeds'' containing not one but several nonzero sites are found to be similar to those of fig. 2, at least on scales much larger than the region of nonzero initial sites, and exhibit the same fractal dimensions. The generation of self-similar patterns is thus a generic feature of cellular automaton evolution from simple ``seeds''. This result may provide some explanation for the widespread occurrence of self similarity in natural systems [9], and suggests the appearance of fractal dimensions and .

previous  l  next