- Term Papers, Book Reports, Research Papers and College Essays

The Evolution of Cellular Automata from Simple Seeds

Essay by   •  September 12, 2010  •  Research Paper  •  4,060 Words (17 Pages)  •  2,187 Views

Essay Preview: The Evolution of Cellular Automata from Simple Seeds

Report this essay
Page 1 of 17

This section discusses patterns formed by the evolution of cellular automata from simple seeds. The seeds consist of single nonzero sites, or small regions containing a few nonzero sites, in a background of zero sites. The growth of cellular automata from such initial conditions should provide models for a variety of physical and other phenomena. One example is crystal growth. The cellular automaton lattice corresponds to the crystal lattice, with nonzero sites representing the presence of atoms or regions of the crystal. Different cellular automaton rules are found to yield both faceted (regular) and dendritic (snowflake-like) crystal structures. In other systems the seed may correspond to a small initial disturbance, which grows with time to produce a complicated structure. Such a phenomenon presumably occurs when fluid turbulence develops downstream from an obstruction or orifice. (3)

Figure 2 shows some typical examples of patterns generated by the evolution of two-dimensional cellular automata from initial states containing a single nonzero site. In each case, the sequence of two-dimensional patterns formed is shown as a succession of ``frames.'' A space-time ``section'' is also shown, giving the evolution of the center horizontal line in the two-dimensional lattice with time. Figure 3 shows a view of the complete three-dimensional structures generated. Figure 4 gives some examples of space-time sections generated by typical one-dimensional cellular automata.

Examples of classes of patterns generated by evolution of two-dimensional cellular automata from a single-site seed. Each part corresponds to a different cellular automaton rule. All the rules shown are both rotation and reflection symmetric. For each rule, a sequence of frames shows the two-dimensional configurations generated by the cellular automaton evolution after the indicated number of time steps. Black squares represent sites with value 1; white squares sites with value 0. On the left is a space-time section showing the time evolution of the center horizontal line of sites in the two-dimensional lattice. Successive lines correspond to successive time steps. The cellular automaton rules shown are five-neighbor square outer totalistic, with codes (a) 1022, (b) 510, (c) 374, (d) 614 (sum modulo 2 rule), (e) 174, (f) 494.

With some cellular automaton rules, simple seeds always die out, leaving the null configuration, in which all sites have value zero. With other rules, all or part of the initial seed may remain invariant with time, yielding a fixed pattern, independent of time. With many cellular automaton rules, however, a growing pattern is produced.

View of three-dimensional structures formed from the configurations generated in the first 24 time steps of the evolution of the two-dimensional cellular automata shown in Fig. 2. Rules (a), (b), and (c) all give rise to configurations with regular, faceted, boundaries. Rules (d), (e), and (f) yield dendritic patterns. In this and other three-dimensional views, the shading ranges periodically from light to dark when the number of time steps increases by a factor of two. The three-dimensional graphics here and in Figs. 10 and 14 is courtesy of M. Prueitt at Los Alamos National Laboratory.

Examples of classes of patterns generated by evolution of one-dimensional cellular automata from a single-site seed. Successive time steps are shown on successive lines. Nonzero sites are shown black. The cellular automaton rules shown are totalistic nearest-neighbor (), with possible values at each site: (a) , code 14, (b) , code 6, (c) , code 10, (d) , code 21, (e) , code 102, (f) , code 138. Irregular patterns are also generated by some , rules (such as that with totalistic code 10), and by asymmetric , rules (such as that with rule number 30).

Rule (a) in Figs. 2 and 3 is an example of the simple case in which the growing pattern is uniform. At each time step, a regular pattern with a fixed density of nonzero sites is produced. The boundary of the pattern consists of flat (linear) ``facets,'' and traces out a pyramid in space-time, whose edges lie along the directions of maximal growth. Sections through this pyramid are analogous to the space-time pattern generated by the one-dimensional cellular automaton of Fig. 4(a).

Cellular automaton rule (b) in Figs. 2 and 3 yields a pattern whose boundary again has a simple faceted form, but whose interior is not uniform. Space-time sections through the pattern exhibit an asymptotically self-similar or fractal form: pieces of the pattern, when magnified, are indistinguishable from the whole. Figure 4(b) shows a one-dimensional cellular automaton that yields sections of the same form. The density of nonzero sites in these sections tends asymptotically to zero. The pattern of nonzero sites in the sections may be characterized by a Hausdorff or fractal dimension that is found by a simple geometrical construction to have value .

Self-similar patterns are generated in cellular automata that are invariant under scale or blocking transformations. Particular blocks of sites in a cellular automaton often evolve according to a fixed effective cellular automaton rule. The overall behavior of the cellular automaton is then left invariant by a replacement of each block with a single site and of the original cellular automaton rule by the effective rule. In some cases, the effective rule may be identical to the original rule. Then the patterns generated must be invariant under the blocking transformation, and are therefore self-similar. (All the rules so far found to have this property are additive.) In many cases, the effective rule obtained after several blocking transformations with particular blocks may be invariant under further blocking transformations. Then if the initial state contains only the appropriate blocks, the patterns generated must be self-similar, at least on sufficiently large length scales.

Cellular automaton (c) gives patterns that are not homogeneous, but appear to have a fixed nonzero asymptotic density. The patterns have a complex, and in some respects random, appearance. It is remarkable that simple rules, even starting from the simple initial conditions shown, can generate patterns of such complexity. It seems likely that the iteration of the cellular automaton rule is essentially the simplest procedure by which these patterns may be specified. The cellular automaton rule is thus ``computationally irreducible'' (cf. Ref. 19).

Cellular automata (a), (b), and (c) in Figs. 2 and 3 all yield patterns whose boundaries have a simple faceted form. Cellular automata (d), (e), and (f) give instead patterns with corrugated, dendritic, boundaries. Such complicated boundaries can



Download as:   txt (25 Kb)   pdf (258.5 Kb)   docx (17.2 Kb)  
Continue for 16 more pages »
Only available on