Transition Rules

The state of every cell is updated once each cycle, according to transition rules, which take into account the cell s current state and the state of cells in the neighborhood. Transition rules may be deterministic, so that the next state of a cell is determined unambiguously by the current state of the CA, or partly or wholly stochastic. 

Transition rules are applied in parallel to all cells, so the state to be adopted by each cell in the next cycle is determined before any of them changes its current state. Because of this feature, CA models are appropriate for the description of processes in which events occur simultaneously and largely independently in different parts of the system and, like several other AI algorithms, are well-suited to implementation on parallel processors. Although the states of the cells change as the model runs, the rules themselves remain unchanged throughout a simulation. 

If the state of a cell in the next cycle is determined by its current state and those of its neighbors, organized — even attractive — behavior may emerge as the entire CA evolve. Suppose that the transition rules for a one-dimensional, two-state (0 and 1) CA model are 

If the sum equals 0 or 3 the state of the cell in the next cycle will be 0, otherwise it will be 1. 

The evolution of a one-dimensional, two-state cellular automaton. The starting state is at the bottom of the figure and successive generations are drawn one above the other. The transition rules are given in the text. 

A cellular automata simulation of a dynamic system provides two classes of information. The first, a visual display, may be very informative of the char- 

It is customary to collect data from several runs, averaging the counts over those runs. The number of iterations performed depends on the system under study. The data collection may be over several iterations following the achievement of a stable or equilibrium condition. This stability is reckoned as a series of values that exhibit a relatively constant average value over a number of iterations. In other words, there is no trend observed toward a higher or lower average value. 

From typical simulations used in the study of aqueous systems, several attributes are customarily recorded and used in comparative studies with properties. These attributes used singly or in sets are useful for analyses of different phenomena. Examples of the use and significance of these attributes will be offered in a later part of this chapter. The designations are 

U fraction of cells bound to four other cells. 

---

Discrete dynamics at each discrete unit time, each cell updates its current state according to a transition rule taking into account the states of cells in its neighborhood. 

Non-homogeneous CA. These are CA 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 rules randomly distributed throughout the lattice. Kauffman [kauff84] has studied the otlier extreme in whidi tlie lattice is randomly populated with all possible Boolean functions of k inputs. 

EXAMPLE Consider an automaton M with alphabet A (Ti,02,03,0 and transition rule (j given by... 

Dynamical Rule d> E x E x x E —> E, where n specifies the number of cells needed to define the neighborhood of a given cell. Defining M i] to be the neighborhood about cell i, the transition rule is most generally written as... 

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. 

Consider an arbitrary d dimensional, k state CA with neighborhood of size Af and evolving in time according to the transition rule . Denoting the space of all possible rules for this CA by we recall that the number of such rules is = ... 

Recall that difference patterns are simply the space-time patterns of the difference between two evolutions of the same transition rule starting from two different starting configurations. For example, the value of the T site at time t of a difference pattern for a k = 2 global rule and two different initial global states cti(0) and... 

Given any lattice C and arbitrary transition rule we define a natural topology... 

What is the complete behavioral specification of a given transition rule on arbitrary lattices Which topologies yield trivial or complex dynamics What fraction of topologies of given size induce a particular variety of dynamical behavior ... 

The transition rule states that can be replaced by /3 only when it is preceded... 

Using the graph metric function Dij = minpaths[ifli nks i, j -jpath)], we can write a general r-noighborhood CA uafue-transition rule / bi the form... 

The time-evolution of G> then proceeds according to the following transition rules (t) value processors of the general form given above and familiar from CA simulations and (m) link processors, which can be divided into site couplers, linking previously unconnected vertices and site decouplers, which disconnect linked points. Because the topology can be altered only by either a deletion of existing links or an addition of links between pairs of vertices H and j with Dij = 2, the dynamics is strictly local. 

The application of the rather cumbersome expressions defining transition rules is in practice extremely straightforward, as we demonstrate with the following example Consider a graph G defined as a (5 x 5) lattice with some distribution of values (7 = 1 at time T = l (see figure 8.19). We are interested in one global update of the... 

A given rule F is completely defined by the set of sums q, (3 and e. Alternatively, by generalizing our encoding scheme for value rules (equation 2.4), we can conveniently summarize a chosen transition rule by a vector-code... 

Table 8.10 Numbers of possible rules for each of the three types of transition rules. d=niaximum allowable degree and a=maximum sum to be used from partition Aij. Ex- for d=5, we have 4096, 2x10 and Nuj= 2 2x10 . We thus have Nt= 4> iP uj 10 possible...

Computer simulations of these systems require that some measures be taken to prevent possible memory overflows, such as would happen in cases either of pure coupling, where links are continually added and none deleted, or in isolated regions of a graph where for a few sites more neighbors arc added than are allowed by memory. We thus introduce working link transition rules... 

Fig. 8,20 First five iterations of an SDCA system starting from a 4-neighbor Euclidean lattice seeded with a single non-zero site at the center. The global transition rule F consists of totalistic-value and restricted totalistic topology rules C — (26,69648,32904)[3 3[ (see text for rule definitions). Solid sites have <7=1.

Transitions occur constantly in nature molecules change from one tautomeric form to another, radioactive nuclei decay to form other nuclei, acids dissociate, proteins alter their shapes, molecules undergo transitions between electronic states, chemicals react to form new species, and so forth. Transition rules allow the simulation of these changes. 

Some or all of the vertices in each fragment may be representative of a water molecule. The trace of each fragment may be mapped onto a two-dimensional grid (Figure 3.1c). This trace is equated with the mapping of a cellular automaton von Neumann neighborhood. The cellular automata transition rules operate randomly and asynchronously on the central cell, i, in each von... 

The cells in a CA use transition rules to update their states. Every cell uses an identical set of rules, each of which is easy to express and is computationally simple. Even though transition rules are not difficult either to understand or to implement, it does not follow that they give rise to dull or pointless behavior, as the examples in this chapter illustrate. 

At regular intervals as determined by a virtual clock, every cell updates its state, using a rule that depends both on its current state and on the current state of its neighbors. In this first example, in which successive states of the CA are written one below the other, the transition rule is... 

As Example 1 and Example 2 suggest, CA rules are easy to apply using a computer. An early example of a CA with which most computer users are familiar is the Game of Life, 1 2 which is a two-state CA with simple transition rules. This became one of the earliest dynamic screen savers. ... 

The Game of Life is run on a two-dimensional square lattice each cell is either "dead" or "alive." The transition rules are ... 

The simplest possible, and perhaps the least useful, transition rule is ... 

When such a transition rule is applied, the state of each cell and, therefore, of the entire system varies completely unpredictably from one cycle to the next (Figure 6.9), which is unlikely to be of much scientific interest. No information is stored in the model about the values of the random numbers used to determine the next state of a cell, thus once a new pattern has been created using this rule there is no turning back All knowledge of what has gone before has been destroyed. This irreversibility, when it is impossible to determine what the states of the CA were in the last cycle by inspecting the current state of all cells, is a common feature if the transition rules are partly stochastic. It also arises when deterministic rules are used if two different starting patterns can create the same pattern in the next cycle. 

The behavior of CA is linked to the geometry of the lattice, though the difference between running a simulation on a lattice of one geometry and a different geometry may be computational speed, rather than effectiveness. There has been some work on CA of dimensionality greater than two, but the behavior of three-dimensional CA is difficult to visualize because of the need for semitransparency in the display of the cells. The problem is, understandably, even more severe in four dimensions. If we concentrate on rectangular lattices, the factors that determine the way that the system evolves are the permissible states for the cells and the transition rules between those states. 

---