Automata

Cellular automata were constructed by Von Neumann and Ulam as simple models of self-reproducing systems that mimic living systems.The Von Neumann cellular automaton is not so simple and comprises a fairly complex set of rules that specifies how the system evolves in time. Codd devised a much simpler rule that achieves self-reproduction. ° Wiener and Rosenbluth 

Before showing how this can be done, we must first define more precisely what a cellular automaton (CA) is. A CA model for a system is constructed as follows The dynamical evolution is imagined to take place on a set of cells. Each cell is defined by a finite set of values of a dynamical variable = sk-k = l.n. The values of the s in a cell change at discrete time instants according to a rule that depends on the value of s in the cell as well as that of its neighbors. Even very simple rules, 3i, can produce complicated dynamics. In fact, CA rules that are Turing machines, that is, are capable of universal computation, can be devised. 

As a simple example of a CA rule, suppose the cells are arranged in a line and the cell variable takes the values 0 or 1, s e (0,1). Let s i) be the value of s in cell i. Next, we need a rule that tells us how the s i) change with time. Suppose the rule depends on the value of s(i, t), that is, the cell value at time t, and the values of its nearest neighbors at the sites i + 1 and i Because the cell can take only the values 0 and 1, we can enumerate all eight possibilities of (5(i-l)s(i)s(i+1)) (000), (001), (010), (Oil), (100), (101), (110), and (111). If we interpret these strings of zeros and ones as binary numbers, they correspond to the decimal numbers 0-7. The CA rule specifies how the central cell value s(i, t) changes as a result of the values of the neighboring cells s i — l,t)s i, t)s i + 1, t)) — s i, t + 1). An example is Rule 90  

Returning to our theme of pattern formation in reaction-diffusion systems, we show how a simple CA model of an excitable system can be constructed.The main characteristics of an excitable medium, as discussed above, are the presence of a stable steady or resting state and the peculiar form of the evolution back to the resting state after a disturbance. In particular, we saw that if the perturbation exceeded a critical value the system became excited to values of the concentration far from the resting state and then slowly relaxed back to the resting state. During this relaxation, the system was refractory and not susceptible to further perturbation. Consequently, 

consider a cell in isolation from its neighboring cells. If it is in the resting state Q, it will remain there since this is the stable steady state of the system. If it is excited, that is, in the state E, it will first become refractory, and then finally return to the resting state. Thus, it will undergo the series of 

In the following sections, we describe what cellular automata are, how they work, and then we provide examples of their uses. Because much of chemistry is carried out in condensed phases, especially in water, we limit our applications to this medium but point out that extensions to other types of systems are possible. 

To discover and analyze the mathematical basis for the generation of complexity, one must identify simple mathematical systems that capture the essence of the process. Cellular automata are a candidate class of such systems. Cellular automata promise to provide mathematical models for a wide variety of complex phenomena, from turbulence in fluids to patterns in biological growth. 

In the first chapter several traditional types of physical models were discussed. These models rely on the physical concepts of energies and forces to guide the actions of molecules or other species, and are customarily expressed mathematically in terms of coupled sets of ordinary or partial differential equations. Most traditional models are deterministic in nature— that is, the results of simulations based on these models are completely determined by the force fields employed and the initial conditions of the simulations. In this chapter a very different approach is introduced, one in which the behaviors of the species under investigation are governed not by forces and energies, but by rules. The rules, as we shall see, can be either deterministic or probabilistic, the latter leading to important new insights and possibilities. This new approach relies on the use of cellular automata. 

Neumann consisted of a two-dimensional grid of square cells, each having a set of possible states, along with a set of rules. The system he developed eventually employed as many as 29 different possible states for the cells, and was, at the least, clumsy to work with. With the development of modern digital computers, however, it became increasingly clear to a small number of scientists that these very abstract ideas could in fact be usefully applied to the examination of real physical and biological systems, with interesting and informative results [9,10]. 

The present chapter will focus on the practical, nuts and bolts aspects of this particular CA approach to modeling. In later chapters we will describe a variety of applications of these CA models to chemical systems, emphasizing applications involving solution phenomena, phase transitions, and chemical kinetics. In order to prepare readers for the use of CA models in teaching and research, we have attempted to present a user-friendly description. This description is accompanied by examples and hands-on calculations, available on the compact disk that comes with this book. The reader is encouraged to use this means to assimilate the basic aspects of the CA approach described in this chapter. More details on the operation of the CA programs, when needed, can be found in Chapter 10 of this book. 

But just what are cellular automata Mathematician Stephen Wolfram has defined cellular automata as follows [1]  

---

McNamara G R and Zanetti G 1998 Use of the Boltzmann equation to simulate lattice-gas automata Phys. Rev. Lett. 61 2332... 

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. 

Wolfram S 1983 Statistioal meohanios of oellular automata Rev. Mod. Phys. 55 601-44... 

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. 

The remainder of the book is divided into eleven largely self-contained chapters. Chapter 2 introduces some basic mathematical formalism that will be used throughout the book, including set theory, information theory, graph theory, groups, rings and field theory, and abstract automata. It concludes with a preliminary mathematical discussion of one and two dimensional CA. 

The grammars for regular languages can be conveniently specified by finite state transition graphs for the finite automata that recognize them. The vertices of the graph represent the the system states Cj E and the arcs represent the possible input states Uj A. The arrows point to the next state that will result from the initial state when the input on the arc is applied. 

Finite automata such as these are the simplest kind of computational model, and are not very powerful. For example, no finite automaton can accept the set of all palindromes over some specified alphabet. They certainly do not wield, in abstract terms, the full computational power of a conventional computer. For that we need a suitable generalization of the these primitive computational models. Despite the literally hundreds of computing models that have been proposed at one time or another since the beginning of computer science, it has been found that each has been essentially equivalent to just one of four fundamental models finite automata, pushdown automata, linear bounded automata and Turing machines. 

Level Language Class Class of Accepting Automata Memory... 

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,... 

Fig. 3.37 Typical soliton-like evolution of the range r = 3 parity-rule filter automata, starting from an initially disordered state.

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. 

Recall that the basic notions of abstr2ict automata and formal language theory were very briefly touched upon in our introductory survey in section 2.1.5. 

---