1. Introduction

The basic components of cellular automata are discrete. But at least in some cases the aggregrate behaviour of large numbers of these components can be effectively continuous. As a result, it is possible to use cellular automata as models of continuum systems, such as fluids.

The mathematical origins of continuum behaviour in cellular automata are much the same as they are for many physical systems. A gas, for example, consists of many discrete molecules. Nevertheless, on a large scale, it can be described as a fluid.

Several conditions are necessary for the overall behaviour of a system with discrete elements to seem continuous.

First, continuum behaviour must be associated with some kind of extensive quantity. Such a quantity must be additive, and must be conserved in the dynamical evolution of the system. In a gas, one example of such a quantity is particle number. Other examples are energy and momentum.

A continuum system such as a fluid has the feature that its state can be described (locally) by just a few extensive quantities. To describe the precise microscopic state of a real gas one must, of course, specify the precise configuration of molecules. But it is believed that unless the gas is highly rarefied, this precise configuration is irrelevant to the macroscopic behaviour of the gas. Only the values of the few, averaged, extensive quantities are significant, so that a fluid approximation can be used.

The basis for this belief is embodied in the Second Law of thermodynamics. It seems that almost regardless of the initial microscopic configuration, collisions rapidly tend to randomize the configuration of gas molecules, so that at least for macroscopic purposes, it suffices to specify merely the values of certain average quantities.

The true basis for this phenomenon has never been very clear. Some descriptions of it can be given in terms of the apparent increase of coarse-grained entropy. But no fundamental derivation has ever been given. The investigation of cellular automaton models seems likely to provide some new insights.

If microscopic randomization is assumed, then overall continuum behaviour can be derived using statistical mechanics. Based on master or transport equations, one can find partial differential equations satisfied by the densities of the extensive quantities conserved by the cellular automaton evolution.

Thus for example there has been much recent work on cellular automata which reproduce the Navier-Stokes equations for viscous fluid flow (see various other CA'86 posters).

Statistical mechanics, and the continuum equations derived from it, provide a considerably reduced description of the system. There may in fact be many systems with different detailed microscopic dynamics, which nevertheless yield identical large-scale statistical or continuum behaviour. Thus, for example, the Navier-Stokes equations describe the aggregrate behaviour of fluids such as air and water with very different microscopic constitutions.

Given generic macroscopic behaviour, it is important for both theoretical and practical purposes to try and find the simplest microscopic dynamics which can reproduce the macroscopic behaviour. One may, for example, seek the simplest cellular automaton rule which reproduces a particular form of continuum behaviour. (``Simplest'' can be defined for example as requiring minimum storage space and minimum number of logical operations to implement.)

Specific rules which reproduce given macroscopic behaviour can conceivably be produced by explicit construction. Different elements of the rules can for example be arranged to mimic particular forms of particle collisions, and so on. The result of such a procedure will be some rule with the desired behaviour. But it will most likely not be the simplest such rule. Finding the simplest rule is in general a difficult optimization problem.

It is in some respects akin to problems such as logic circuit design in which a device with a particular form of overall behaviour must be constructed with the minimum number of circuit elements. Such problems have recently increasingly been tackled by iterative or adaptive procedures. Some dynamics in the space of possible circuits is defined, and the optimization process consists in applying this dynamics with certain constraints imposed.

Thus one can consider finding minimal cellular automaton rules by various iterative and adaptive procedures.

Such methods are examples of a general approach to computer programming and other design problems which one expects will become increasingly common. At present, most systems are designed in a step-by-step fashion, with their complete progression of states foreseen in detail by the designer. But more efficient designs may potentially be found by a more ``goal-oriented'' approach. Having specified the constraints, a definite adaptive or iterative procedure traverses the space of possible designs, seeking the one which optimizes some measure of success. The result will typically be a more efficient ``computer-generated'' design, whose operation cannot necessarily be ``understood'' in an explicit step-by-step fashion.

This poster considers as an example the problem of finding the simplest cellular automaton rule which reproduces the one-dimensional diffusion equation.

The potential interest of these investigations is severalfold.

1. They may provide practical methods for solving problems related to continuum systems (and these methods may be compared in detail with existing methods).
2. They provide examples of systems which exhibit the basic phenomena of thermodynamics, and should allow further elucidation of the foundations of thermodynamics.
3. They give examples of the procedure of ``adaptive programming''.

next