CA Systems

There are at least as many variants of the basic CA algorithm as there are ways of generalizing the characteristics of a typical CA system. Here are a few general models ... 

Most of the analytical structure of the dynamics of linear CA systems emerges from their field-theoretic properties specifically, those of finite fields and polynomials over fields. A brief summary of definitions and a few pertinent theorems will be presented (without proofs) to serve as reference for the presentation in subsequent sections. 

Although there is an incredibly rich variety of specific CA systems, each of which is carefully defined or selected to fit the requirements of a particular model, the definition of any of these specific, systems requires the specification of each of the following four generic characteristics ... 

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. 

There are a number of additional local structures and properties that appear even in elementary CA systems. Grassberger [grass84b, for example, has observed that rule R22 actually harbors very complex long-range effects, similar to a critical phenomenon (see section 3.1.4). Since the majority of these findings require the use of more general and sophisticated correlation measures than we have defined thus far, we will pick up our discussion of them in chapter 4. 

It turns out, rather fortuitously, that if the desire is to merely obtain an overview of the general types of possible two-dimensional behaviors, then focusing only on T and OT- type rules is not really a restriction, as the set of all possible behaviors is well represented. Having said that, we should be quick to point out that if the desire is instead to study either a class of CA systems with a special set of behavioral characteristics or to find an appropriate CA model for a real physical system, specific rules and/or lattice connectivities and neighborhoods will have to be invented. For our brief introductory look in this section at generic two-dimensional behavior, however, we will be content to restrict ourselves (for the most part) to commentary on T- and OT type rules. 

Dissipative systems whether described as continuous flows or Poincare maps are characterized by the presence of some sort of internal friction that tends to contract phase space volume elements. They are roughly analogous to irreversible CA systems. Contraction in phase space allows such systems to approach a subset of the phase space, C P, called an attractor, as t — oo. Although there is no universally accepted definition of an attractor, it is intuitively reasonable to demand that it satisfy the following three properties ([ruelle71], [eckmanSl]) ... 

The general theory of computability, particularly how it relates to general CA systems, is discussed at some length in chapter 6. 

A partial analogy between the dynamics of CA and the behaviors of continuous dynamical systems may be obtained by exploiting a fundamental property of CA systems namely, continuity in the Cantor-set Topology. We recall from section 2.2.1 that the collection of all one-dimensional configurations, or the CA phase space, r = where E = 0,1,..., fc 9 cr and Z is the set of integers by which each site of the lattice is indexed, is a compact metric space homeomorphic to the Cantor set under the metric... 

While there is, at present, no known CA analogue of a Froebenius-Perron construction, a systematic n -order approximation to the invariant probability distributions for CA systems is readily obtainable from the local structure theory (LST), developed by Gutowitz, et.al. [guto87a] LST is discussed in some detail in section 5.3. 

Second, observe that the methodology need not be constrained to CA systems alone. With a suitable coarse-graining, the same methodology can easily be extended to provide the spectra of continuous dynamical systems, such as onedimensional mappings of the unit interval to itself. 

Many more such relationships can be derived in a similar manner (see [ma85] or [stan71]). For our purposes here, it will suffice to merely take note of the fact that certain relationships among the critical exponents do exist and are in fact commonly exploited. Indeed, we shall soon sec that certain estimates of critical behavior in probabilistic CA system are predicated on the assumptions that (1) certain rules fall into in the same universality class as directed percolation, and (2) the same relationships known to exist among critical exponents in directed percolation must also hold true for PC A (see section 7.2). 

An early study of a stochastic CA system was performed by Schulman and Seiden in 1978 using a generalized version of Conway s Life rule [schul78]. Though there was little follow-on effort stemming directly from this particular paper, the study nonetheless serves as a useful prototype for later analyses. The manner in which Schulman and Seiden incorporate site-site correlations into their calculations, for example, bears some resemblance to Gutowitz, et.ai. s Local Structure Theory, developed about a decade later (see section 5.3). In this section, we outline some of their methodology and results. 

In the context of CA systems, it turns out that there is a difference between rules that are invertible and rules that are time-reversal invariant. A global CA rule S —> S, mapping a global state ct S to some other global state ct S, is said to be invertible if for all states ct S there exists exactly one predecessor state O S such that (cr) = a. The state transition graphs G for all such rules must therefore consist entirely of cycles. 

An obvious, but extremely important, property of reversible CA is that all of the information contained in the initial state can be recovered at any time T merely by running the system backwards in time from the state Sj, Thus, just as there exist as many integrals of the motion as there are variables describing a given mechanical system, the dynamics of reversible CA systems results in as many constants (or... 

A trivial reversible CA consists of a collection of completely isolated systems each site contains only itself in its neighborhood. Since a7 = 1, the rule table and site value sets have the same cardinality. In particular, if the function 21,—> Z is invertible (i.e. if 4> serves merely to permute the elements of the set Zk) then the global CA system is itself reversible. More formally, writing < = tt H/ci where... 

Toffoli [toff7,5] showed that it is possible to realize such conserved landscape permutations in CA systems of arbitrary dimensionality and site value space size I 1= k. In each case, as in the above example, the method defines the inverse along with the forward map. 

As mentioned above, CMLs are simple generalizations of generic CA systems. Confining ourselves for the time being to one-dimension for simplicity, we begin with a one-dimensional lattice of real-valued variables ai t) R whose temporal evolution is given by... 

Some other varieties of behavior are shown in figure 8.22 and 8.23. Figures 8.22-a and 8.22-b are representative of the class of link rules for which the induced structural change is only minimal. Such systems evolve essentially as a CA system on a mildly perturbed underlying lattice. Other rules may have a much stronger effect on the lattice and can significantly alter the manner in which the pure value propagation proceeds in the absence of any link operators. 

Consider the simplest type of L-system namely, a deterministic context-free L-system, also called a DOL-Systeni. As the name implies, the production rules of such systems are allowed to transform only single symbols i.e. the dynamics is independent of all neighboring symbol values. DOL-Systems are thus generalized CA systems that are allowed to add sites but whose local rule depends only on a given site itself and none of its neighbors. 

A schematic representation of emergence is given in figure 12.6, which depicts the first three levels of a dynamical hierarchy and the rules or laws describing their behavior. The first, or lowest, level might be thought of as the level on which a CA system is usually defined. It consists of the lattice sites and values that define the microscopic dynamics. 

While CAM-6 is somewhat limited in its ability to perform large-scale simulations of physical systems (it is a much less capable system than its follow-on, the CAM-8, for example see discussion below), its fundamental historical importance cannot be overstated. CAM-6 allowed researchers to directly experience, for the first time and in real time, the evolution of CA systems theretofore undertsood only as purely conceptual models. Margolus and Toffoli recall that when Pomeau, one of... 

---