Automata, cellular

While there is an enormous variety of particular CA models-each carefully tailored to fit the requirements of a specific system-most CA models usually possesses these five generic characteristics  

While one is free to think of CA as being nothing more than formal idealizations of partial differential equations, their real power lies in the fact that they represent a large class of exactly computable models since everything is fundamentally discrete, one need never worry about truncations or the slow aciminidatiou of round-off error. Therefore, any dynamical properties observed to be true for such models take on the full strength of theorems [toff77a]. 

Exact computability in this sense, however, is achieved only at the cost of being able to obtain approximate solutions. Perturbation analysis, for example, is rendered virt ially meaningless in this context. It is not s irprising that traditional investigatory methodologies are not very well suited to studies of complex systems. Since the behavior of such models can generally be obtained only through explicit simulation, the computer becomes the one absolutely indispensable research tool. 

Numerous systems in science change with time or in space plants and bacterial colonies grow, chemicals react, gases diffuse. The conventional way to model time-dependent processes is through sets of differential equations, but if no analytical solution to the equations is known, so that it is necessary to use numerical integration, these may be computationally expensive to solve. 

In the cellular automata (CA) algorithm, many small cells replace the differential equations by discrete approximations in suitable applications the approximate description that the cellular automata method provides can be every bit as effective as a more abstract equation-based approach. In addition, while differential equations rarely help a novice user to develop an intuitive understanding of a process, the visualization provided by CA can be very informative. 

Using Artificial Intelligence in Chemistry and Biology A Practical Guide 

The method is different in nature from the techniques discussed elsewhere in this book because, despite the fact that the cells that comprise a CA model evolve, they do not learn. The lack of a learning mechanism places the method at the boundaries of Artificial Intelligence, but the algorithm still has features in common with AI methods and offers an intriguing way to solve scientific problems. 

From Fig. 7.13, it is seen that it would be desirable to have the acceleration ipi with the same sign as —Fipt. This is equivalent to increase the changes that lower the corresponding orbital energy, and to suppress the changes that make i1 higher. The ipi spinorbitals obtained in the numerical integration have to be corrected for orthonormality, as is assured by the second term in (7.19). 

The prize for the elegance of the Car-Parrinello method is the computation time, which allows one to treat systems currently up to a few hundreds of atoms (while MD may even deal with a million of atoms). The integration interval has to be decreased by a factor of 10 (i.e. 0.1 fs instead of 1 fs), which allows us to reach simulation times of the order of 10-100 picoseconds instead of (in classical MD) nanoseconds. 

Another powerful tool for chemists is the cellular automata method invented by John (in his Hungarian days Janos) von Neumann and Stanislaw Marcin Ulam (under the name of cellular spaces ). The cellular automata are mathematical models in which space and time both have a granular structure (similar to Monte Carlo simulations on lattices, in MD only time has such a structure). A cellular automaton consists of a periodic lattice of cells (nodes in space). In order to describe the system locally, we assume that every cell has its state representing a vector of N components. Each component is a Boolean variable, i.e. a variable having a logical value (e.g., 0 for false and 1 for tive ). 

For physically relevant states, the propagation and collision rules for the behaviour of such a set of cells as time goes on, may mirror what would happen with a physical system. This is why cellular automata are appealing. Another advantage is that due to the locality mentioned above, the relevant computer programs may be effectively parallelized, which usually significantly speeds up computations. The most interesting cellular automata are those for which the rules are of a non-linear character (cf. Chapter 15). 

One of the simplest examples pertains to a lattice model of a gas. Let the lattice be regular two-dimensional (Fig. 7.14). 

---

In favourable contrast to molecular dynamics, BD allows molecular movements of realistically long duration to be simulated. Nevertheless, the practical number of protein molecules which can be simulated is only two since collective phenomena are often of crucial importance in detennining the course of interaction events, other simulation teclmiques, such as cellular automata [115], need to be used to capture the behaviour of large numbers of particles. 

Recently a cellular automata version of the DD model has been studied [87]. The reported results are in qualitative agreement with Monte Carlo simulations [83,84]. Also, mean-field results [87] are in agreement with those early obtained in [85]. Very recently, simulations of the kinetic behavior of the DD model have been reported [88]. 

S. Mourachov. Cellular automata simulation of the phenomenon of multiple crystallization. Comput Mater Sci 7 384, 1997. 

Toffoli Applied cellular automata directly to modeling physical laws... 

Wolfram Wrote a landmark review article on properties of cellular automata that effectively legitimized the field as research endeavor for physicists... 

Toffoli, Wolfram First cellular automata conference held at MIT, Boston... 

Table 1.1 Some landmark historical developments in the study of cellular automata and complex systems.

Other important historical landmarks include the founding, in 1984, of the Santa Fe Institute, which is one of the leading interdisciplinary centers for complex systems theory research the first conference devoted solely to research in cellular automata (which is a prototypical mathematical model of complex systems), organized by Farmer, Toffoli and Wolfram at MIT in 1984 [farmer84] and the first artificial life conference, organized by Chri.s Langton at Los Alamos National Laboratory, in 1987 [lang89]. 

Chate and Manneville [chate92] have examined a wide variety of cellular automata that live in dimensions four, five and higher. They found many interesting rules that while being essentially featureless locally, nonetheless show a remarkably ordered global behavior. 

Probabilistic CA. Probabilistic CA are cellular automata in which the deterministic state-transitions are replaced with specifications of the probabilities of the cell-value assignments. Since such systems have much in common with certain statistical mechanical models, analysis tools from physics are often borrowed for their study. Probabilistic CA are introduced in chapter 8. 

Quantum Cellular Automata (QCA) in order to address the possibly very fundamental role CA-like dynamics may play in the microphysical domain, some form of quantum dynamical generalization to the basic rule structure must be considered. One way to do this is to replace the usual time evolution of what may now be called classical site values ct, by unitary transitions between fe-component complex probability- amplitude states, ct > - defined in sncli a way as to permit superposition of states. As is standard in quantum mechanics, the absolute square of these amplitudes is then interpreted to give the probability of observing the corresponding classical value. Two indepcuidently defined models - both of which exhibit much of the typically quantum behavior observed in real systems are discussed in chapter 8.2,... 

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. 

---