2. The Approach

The diffusion equation can be derived by considering the behaviour of the aggregate density of a large number of particles, each of which executes a random walk. The random walk may result from collisions with other particles of the same kind (as in self diffusion), or from interactions with some separate stochastic background.

The overall statistical behaviour of random walks is well known to be highly insensitive to the precise details of the walk. Thus for example walks whose steps are constrained to lie on various discrete lattices give in the large scale limit the same statistical behaviour as walks whose steps have no constraints.

By constructing a cellular automaton rule which involves various discrete particles, whose total number is conserved, one should thus be able to reproduce the diffusion equation.

A crucial issue, which relates to the foundations of thermodynamics, is the degree of randomness which is produced by a cellular automaton, or which, for that matter, is really necessary to reproduce macroscopic diffusion phenomena.

Nevertheless, following the approach discussed in the introduction, one is concerned not merely with finding some cellular automaton rule which reproduces diffusion, but rather with finding the simplest or optimal one. One must delineate a class of rules capable of reproducing diffusion, and then search within these to find the optimal one.

The conservation laws necessary for macroscopic diffusion turn out to be quite straightforward to ensure in a class of cellular automata. The capability for randomness generation cannot, it seems, be guaranteed directly by the structure of the rule, but must rather be deduced by studying the explicit behaviour of the system.

Diffusion requires that a scalar quantity (which in some cases can be identified as a particle number) is additively conserved.

In the simplest cellular automata, one considers rules which specify the new value of a single site in terms of the values of a neighbourhood of sites around it on the previous time step. In most such rules, no additive quantities can be conserved. In addition, such rules are usually highly irreversible, so that they evolve towards attractors which contain only a subset of the possible states. The accessibility of only a subset of states makes an adequate degree of randomness less likely. It does however necessarily preclude diffusion equation behaviour; the various statistical mechanical tools used in derivations can still be applied, but now not to all possible states, but only to those on the attractor.

There are several methods for constructing classes of cellular automata whose evolution satisfies certain conservation laws. (See Y. Pomeau ``Invariant in cellular automata'', J. Phys. A17 (1984) L415 and N. Margolus ``Physics-like models of computation'', Physica 10D (1984) 81, both reprinted in Theory and Applications of Cellular Automata (edited by S. Wolfram).) The method used here involves considering cellular automata which map one block of sites into another block of the same size.

In the simplest case, one considers a one-dimensional cellular automaton which maps pairs of binary site values to other pairs of binary values. The dynamics is chosen to be such that the boundaries of the pairs are taken to be at even and at odd sites on alternate time steps.

Figure 2.1 shows patterns generated by all the possible cellular automata of this kind. A variety of phenomena are observed.

Most of the cellular automata of this class show neither additive conservation laws nor reversibility. But unlike cellular automata whose rules are constructed in the usual way, the conditions for conservation and reversibility in these blocked cellular automata are comparatively simple to state.

The condition for reversibility is simply that the mapping from one set of blocks to another be a permutation (so that this mapping is invertible). (There are 24 such rules in the set shown in figure 2.1.)

The condition for additive conservation laws is that for some values and the quantity be conserved, where is the number of sites with value in each possible block.

Table 2.1 gives the possible rules which satisfy this condition. Two are reversible; two are not. Inspection of figure 2.1 shows that in none of the cases is sufficient randomness generated.

As a result, one must conclude that two possible values at each site () and block size 2 () are not sufficient to yield diffusion equation behaviour.

[ Figure 2.1 ] Patterns generated by evolution from disordered initial states according to all possible one-dimensional , blocked cellular automaton rules. These rules have 2 possible values at each site. They are updated by mapping each block of two adjacent sites on to another block of two sites. On one ``half step'', blocks which begin on even-numbered sites are updated; on the other ``half step'', blocks beginning at odd-numbered sites are updated. The rules are numbered as follows. The output blocks for each of the possible input blocks 11, 10, 01 and 00 are written down in order. Then each output block is converted to a base 4 digit. The resulting base 4 number is then quoted in base 10.

[ Table 2.1 ] , block cellular automaton rules as illustrated in figure 2.1, with certain conservation laws relating to the total numbers of sites with values .

It turns out that , is also not sufficient.

As a result, one must consider , rules. (A rough estimate of the ``complexity'' of rules can be obtained from the number of bits necessary, without compression, to specify their complete rule tables. This number is given by . It is slightly larger for , than for , .)

With , there is slightly more freedom in the definition of additive quantities. One might, for example, consider adding the numerical values of sites. It turns out, again, that the set of rules with this quantity conserved is too highly constrained to allow a sufficient degree of randomness generation.

An alternative class of rules are those which conserve not the sum of the numerical values of sites, but the total number of binary bits contained in these values. There are 16 possible rules which satisfy this condition, and are reversible. Patterns generated by them are illustrated in figure 2.2.

Some of these rules obviously do not show sufficient randomness to yield diffusion behaviour. But others require more sophisticated analysis.

[ Figure 2.2 ] Patterns generated by all , rules which are reversible and conserve the number of binary bits in each configuration. These rules are candidates for simulation of the one-dimensional diffusion equation.

previous  l  next