Cellular automata rules

Langton wais able to provide a tentative answer to his question by examining the behavior of the entire rule space of elementary one-dimensional cellular automata rules (see discussion in section 3.2) as parameterized by a single parameter A. He found that as A is increased from its minimal to maximal values, a path is effectively traced in the rule space that progresses from fixed point behavior to simple period-... 

Richards, et. al. s idea is to use a genetic algorithm to search through a space of a certain class of cellular automata rules for a local rule that best reproduces the observed behavior of the data. Their learning algorithm (which was applied specifically to sequential patterns of dendrites formed by NH4 Br as it solidifies from a supersaturated solution) starts with no a-priori knowledge about the physical system. R, instead, builds increasingly sophisticated models that reproduce the observed behavior. 

For the particular class of reversible cellular automata rules, we might also add the fourth property ... 

To set up the problem and in order to appreciate more fully the difficulty in quantifying complexity, consider figure 12.1. The figure shows three patterns (a) an area of a regular two-dimensional Euclidean lattice, (b) a space-time view of the evolution of the nearest-neighbor one-dimensional cellular automata rule RllO, starting from a random initial state,f and (c) a completely random collection of dots. 

Consider the evolution of the nearest-neighbor one-dimensional cellular automata rule RllO, starting from a random initial state. A few early steps of a sample evolution are shown in figure 12.11. 

Ii90a] Li, W., N.H.Packard and C.G.Langton, Transition phenomena in cellular automata rule space , Physica, 45D (1990) 77-94. 

Ii90b] Li, W. and N.Packard, The structure of the elementary cellular automata rule space . Complex Systems, 4 (1990) 281-297. 

Interesting sounds may be achieved using this technique, but the specification of suitable cellular automata rules can be slightly difficult. However, once the electronic musician has been gripped by the fascinating possibilities of this technique, an intuitive framework for the specification of cellular automata rules should naturally emerge for example, a rule of a growing type of behaviour (i.e. more and more cells are activated in time) invariably produces sounds whose spectral complexity increases with time. 

Jacques Chareyron classifies the output of LASy into three main groups, according to the type of cellular automata rules employed (Chareyron, 1990) ... 

Sounds with simple evolution but with no ending by increasing the complexity of the cellular automata rules one obtains endless successions of similar but not completely identical waveforms... 

Figure 1,8, for example, plots the probability that a cell has value 1 at time t4-l - labeled Pt+i - versus the probability that a cell had value 1 at time t -labeled Pt - for a particular four dimensional cellular automaton rule. The rule itself is unimportant, as there are many rules that display essentially the same kind of behavior. The point is that while the behavior of this rule is locally featureless - its space-time diagram would look like noise on a television screen - the global density of cells with value 1 jumps around in quasi-periodic fashion. We emphasize that this quasi-periodicity is a global property of the system, and that no evidence for this kind of behavior is apparent in the local dynamics. 

Richards, Meyer and Packard [richa90] have suggested a way to extract two-dimensional cellular automaton rules directly from experimental data. The same idea, outlined below, can in principle be used in more general contexts. 

Ievine92] Levine L., Regular language invariance under one-dimensional cellular automaton rules, Complex Systems 6 (1992) 163-178. 

Figure 9.12a. Schematic drawing of cellular automaton rule spaces indicating relative location of periodic, chaotic and complex regimest L...

Cellular automata can be constructed as simplified models of reaction-diffusion systems. Often the main features of an apparently very complex dynamics can be captured in a simple rule. The Greenbeig-Hastings rules [13] are an example of simple cellular automaton rules that model excitable media. We term such cellular automaton models classical cellular automata since they are constructed in the spirit of the original cellular automaton models of Von Neumann. There is a laige literature [14] on this topic that deals with the mathematical properties of different abstract cellular automaton rules [15], as well as studies that attempt to model rather detailed features of specific reaction-diffusion equations [16,17]. 

Eloranta, K. and Nummelin, E. (1992) The kink of cellular automaton rule 18 performs a random walk. Journal of Statistical Physics, 69 1131-1136. 

Richards, F. C., Meyer, T. R, and Packard, N. H. (1990) Extracting cellular automaton rules directly from experimental data. Physica D 45 189-202. 

Conway Introduced two-dimensional cellular automaton Life rule... 

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

Although LB therefore nowadays may be considered as a solver for the NS equations, there is definitely more behind it. The method originally stems from the lattice gas automaton (LGA), which is a cellular automaton. In a LGA, a fluid can be considered as a collection of discrete particles having interaction with each other via a set of simple collision rules, thereby taking into account that the number of particles and momentum is conserved. 

Many important natural processes ranging from nuclear decay to uni-molecular chemical reactions are first order, or can be approximated as first order, which means that these processes depend only on the concentration to the first power of the transforming species itself. A cellular automaton model for such a system takes on an especially simple form, since rules for the movements of the ingredients are unnecessary and only transition rules for the interconverting species need to be specified. We have recently described such a general cellular automaton model for first-order kinetics and tested its ability to simulate a number of classic first-order phenomena.70... 

Fig. 7.16. Operation of a cellular automaton-a model of gas. The particles occupy the lattice nodes (cellsl. Their displacement from the node symbolizes which direction they are heading on with the velocity equal to 1 length unit per 1 time step. In the left scheme (a), the initial situation is shown. In the right scheme the result of the one step propagation and one step collision is shown. Collision only took place in one case (at 03 2). collision rule has been applied (of the lateral outgoing). The game would...

Two other approaches treat a spatially distributed system as consisting of a grid or lattice. The cellular automaton technique looks at the numbers of particles, or values of some other variables, in small regions of space that interact by set rules that specify the chemistry. It is a deterministic and essentially macroscopic approach that is especially useful for studying excitable media. Lattice gas automata are mesoscopic (between microscopic and macroscopic). Like their cousins, the cellular automata, they use a fixed grid, but differ in that individual particles can move and react through probabilistic rules, making it possible to study fluctuations. 

Partial differential equations represent one approach (a computationally intensive one) to simulating reaction-diffusion phenomena. An alternative, more approximate, but often less expensive and more intuitive technique employs cellular automata. A cellular automaton consists of an array of cells and a set of rules by which the state of a cell changes at each discrete time step. The state of the cell can, for example, represent the numbers of particles or concentrations of species in that cell, and the rules, which depend on the current state of the cell and its neighbors, can be chosen to mimic diffusion and chemical reaction. 

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. 

LASy instruments are defined in terms of an initial waveform, a rule for the cellular automaton (referred to as the transition rule) and envelopes for amplitude and pitch. The system provides tools for the individual specification of these components so that the user can build their own library of waveforms, rules and envelopes (Figure 8.16). Instruments are either created by combining components selected from these libraries or from scratch on a window, where the user can set up all these parameters at once (Figure 8.17). 

Figure 8.16 LASy instruments are defined in terms of an initial waveform, a rule for the cellular automaton and envelopes for amplitude and pitch...

---