CA rules

Asynchronous CA. CA rules are typically defined so that all lattice sites update their values simultaneously throughout the lattice on each time step. A natural generalization is to lift this restriction by allowing asynchronous updates [inger84]. 

Because of the rather large total number of possible rules, it is frequently convenient to deal with more restricted classes. As we will later see, however, it is rather fortuitous that most, if not all, of the characteristic behavior of generic CA rules is nonetheless retained. 

It is easy to see that an elementary size-n one-dimensional CA rule (f) is equivalent to a size-n feedback shift register with a G (0,1, taps at positions n — 2, n — 1 and n, and f 4>. The only difference is that it takes n shift-register time-steps to reproduce a single CA time step. 

The extension of generic CA systems to two dimensions is significant for two reasons first, the extension brings with it the appearance of many new phenomena involving behaviors of the boundaries of, and interfaces between, two-dimensional patterns that have no simple analogs in one-dimension. Secondly, two-dimensional dynamics permits easier (sometimes direct) comparison to real physical systems. As we shall see in later sections, models for dendritic crystal growth, chemical reaction-diffusion systems and a direct simulation of turbulent fluid flow patterns are in fact specific instances of 2D CA rules and lattices. 

Non-Homogeneous CA a characteristic feature of all CA rules defined so far has been that of homogeneity - each cell of the system evolves according to the same rule 0. Hartman and Vichniac [hartSfi] were the first to systematically study a class of inhomogeneous CA (INCA), in which the state-transition rules are allowed to vary from cell to cell. The simplest such example is one where there are only two different 0 s, which are randomly distributed throughout the lattice. Kauffman has studied the other extreme in which the lattice is randomly populated with all 2 possible boolean functions of k inputs. The results of such studies, as well as the relationship with the dynamics of random, mappings, are covered in detail in chapter 8.3. 

Simulation of 4>i by d>2 implies the existence of a set A C A for which the evolution under the two rules 4>i and [Pg.67]

Many, possibly all, rules appear to generate asymptotic states which are block-related to configurations evolving according to one of only a small subset of the set of all rules, members of which are left invariant under all block transformations. That is, the infinite time behavior appears to be determined by evolution towards fixed point rule behavior, and the statistical properties of all CA rules can then, in principle, be determined directly from the appropriate block transformations necessary to reach a particular fixed point rule. 

As noted repeatedly in earlier sections, CA rules are generally irreversible a given configuration typically has more than one predecessor. Although it is difficult to write down a reversible rule - for which each configuration has a unique predecessor - from scratch, there is a very simple way of turning an arbitrary (r, k) CA rule, 0, that is first-order in time into a second-order reversible rule, (f-jz-f... 

Consider the behavioral changes induced in a randomly chosen one-dimensional CA rule such that A is successively and minimally incremented from 0 to 1. As an example, let us take fc = 4 and r = 2 (i.e. neighborhood size M = 2r + 1), and use a lattice of = 128 sites with periodic boundary conditions. We summarize a typical sequence of induced behavioral cdianges ... 

Plate 1. A space-time plot of a Wolfram class-4 one-dimensional fc = 10 (i.e. 10 state), radius r = 6 totalistic CA rule. 

Plate 3. A snapshot of a Cyclic Cellular Automata (CCA) rule, which is a typical representative of a class of CA rules first introduced by David Griffeath (see http // psoup.math.wisc.edu/ kitchen.html). In this example, 14 colors are arranged cyclically. Bach color advances to the next, with the last color cycling back to 0. Each update of a site s color advances that color by 1 if there are at least a threshold number of sites of the next color within that site s neighbourhood. The example shown in this figure uses the 4-neighbor von Neumann neighbourhood. See Chapter 8. 

The time evolution of the discrete-valued CA rule, F —> F, is thus converted into a two-dimensional continuous-valued discrete-time map, 3 xt,yt) —> (a y+i, /y+i). This continuous form clearly facilitates comparisons between the long-time behaviors of CA and their two-dimensional discrete mapping counter-... 

Figure 4.12 shows sample a vs y plots obtained in this manner for a few elementary CA rules. Note that the patterns for nonlinear rules such as R18, R22, and 122 appear to possess a characteristic fractal-like structure reminiscent of the strange attractors appearing in continuous systems shown earlier. We will comment on the nature of this similarity a bit later on in this chapter. 

We recall from section 3,1,2 that a difference pattern is a space-time pattern of the difference between two evolutions of the same rule starting from two different initial states. For k = 2 CA rules 4>, for example, the value of the T site on the... 

The values of all of the sites contained within the B x T) dotted inner region of this figure are completely determined by the values in the outer lined region. Since this surrounding area contains B- -2r T — 1)) sites (where V is, as usual, the range of the given CA rule), we have that... 

Given any arbitrary local range-r one-dimensional CA rule, (/> 0,1,... fe —... 

Despite being notoriously difficult to analyze formally, the behavior of general CA rules is nonetheless often amenable to an almost complete mathematical characterization. In this section we look at a simple method that exploits the properties of certain implicit deterministic structures of elementary one-dimensional rules to help determine the existence of periodic temporal sequences, rule inverses and homogeneous states. Additional details appear in [jen86a] and[jen86b]. 

Theorem 1 Let be an elementary CA rule belonging either to deterministic structure type (1) (see table 5.1) with 100 —t 04 = 1 or type (2) with 001 > ai = 1. Then, with arbitrary finite initial states, there can exist at most one periodic sequence. 

The following theorem defines the class of CA rules under which finite initial states evolve to homogencious states, and thus describes all class cl rules ... 

The following theorem - stated without proof (see [jen86a]) - gives necessary and sufficient conditions for CA rules to generate constant temporal sequences ... 

This same technique can be used to find the number of limit cycles of period p on lattice size n for any two-neighbor CA rule. 

---