Problem 9

What is the correspondence between cellular automata and continuous systems?

Cellular automata are discrete in several respects. First, they consist of a discrete spatial lattice of sites. Second, they evolve in discrete time steps. And finally, each site has only a finite discrete set of possible values.

The first two forms of discreteness are addressed in the numerical analysis of approximate solutions to, say, differential equations. It is known that so long as a ``stable'' discretization is used, the exact continuum results are approximated more and more closely as the number of sites and the number of time steps is increased. It is possible to devise cellular automaton rules that provide approximations to partial differential equations in this way. In the simplest cases, however, the approximations are of the Jacobi, rather than the Gauss-Seidel kind, in that the algorithm for calculating new site values uses the old values of all the neighbours, rather than the new values of some of them. This can lead to slow convergence and instabilities in some cases.

The third form of discreteness in cellular automata is not so familiar from numerical analysis. It is an extreme form of round-off, in which each ``number'' can have only a few possible values (rather than the usual say or ). It is not clear what aspects of, say, differential equations are preserved in such an approximation. However, preliminary studies in a few cases suggest that the overall structure of solutions to the equations are remarkably insensitive to such approximations. If the cellular automaton approximates for example a continuous field, then the value of the field at a particular point could correspond roughly to the density of say nonzero sites around that point: the values of individual field points would be represented in a distributed manner, just as they often are in actual physical systems. Explicit examples of cellular automaton approximations to partial differential equations of physical importance would be valuable.

There are some aspects of nonlinear differential equations that may well have rather direct analogues in cellular automata. For example, the persistent propagating structures found in class 4 cellular automata may well be related to solitons in nonlinear differential equations, at least in their solitary persistence, if not in their interactions. Similarly, the overall topological forms of some of the patterns generated by two and higher dimensional cellular automata [29] may correspond to those generated say by reaction-diffusion equations [30]. Moreover, many highly-nonlinear partial differential equations give solutions that exhibit discrete or cellular structure on some characteristic length scale (e.g., [31]). The interactions between components in the cellular structure cannot readily be described by a direct discretization of the original differential equation, but a cellular automaton model for them can be constructed.

Continuum descriptions may be given of many of the large-scale structures that occur in cellular automata. For example, the motion of domain walls between phases may be described by diffusion-like differential equations. A very direct continuum approximation to a cellular automaton is provided by a mean field theory, in which only the average density of sites, and not their individual values, is considered [2]. Presumably in the limit of large spatial dimensionality, this approximation should become accurate. But in one or two dimensions, it is usually quite inadequate, and gives largely misleading results. Large-scale phenomena in cellular automata occur as collective effects involving many individual sites, and the particular rules that relate the values of these sites are significant.

previous  l  next