4. The Winning Rule

The phenomenon of randomization from simple initial conditions occurs in some but not all of the candidate diffusion equation cellular automata of figure 2.2. Figure 4.1 shows evolution from a simple initial condition for all of these rules. Only one rule, and its (2,1) conjugate, show randomization in this case. Figure 4.2 shows the longer time evolution of this rule, on a size 80 with periodic boundary conditions. Regularities are still seen, but many features seem random.

[ Figure 4.1 ] Patterns generated by the , blocked cellular automata of figure 2.2, starting from a simple initial condition. The cellular automata are shown on a size 80 lattice with periodic boundary conditions. The initial condition consists of a block of 20 sites with value 1 in the centre of the system. Most of the rules are seen to give rise to simple periodic patterns.

The degree of randomness generated by this rule can be tested by applying certain statistical procedures. A simple one is the computation of coarse-grained entropy. Figure 4.3 shows the coarse-grained entropy for the system. It is seen to tend rapidly to a maximum value, as expected for an apparently random system.

Table 4.1 gives the block transformations for this rule. Interpretations in terms of particles and so on can be given. But it is noteworthy that making the rule ``increasingly mixing'' by including transitions for various other blocks does not yield an increase in the randomness of the overall behaviour. In fact, as figures 2.2 and 4.1 show, such ``additional mixing'' usually leads to simpler overall behaviour.

[ Figure 4.2 ] Longer sequences generated by one rule from figure 4.1 which seems to generate randomness from simple initial conditions. The patterns on this page were made on a size 80 lattice, with a size 20 initial block. The patterns on the next page were made with a size 21 initial block. The degradation of orderly initial conditions into apparent randomness is clearly visible in these pictures.

[ Figure 4.3 ] Time development of the coarse-grained entropy associated with the process of figure 4.2. The density of bits was computed in 10 bins across the system. Then the densities found were combined to give the entropy This coarse-grained entropy is seen to tend to a maximum, as expected from the Second Law of thermodynamics.

The large scale average density of bits in evolution according to the rule of table 4.1 should satisfy a diffusion equation. Figure 4.4 shows the microscopic dynamics of this rule for the cases of low and high bit density. At low bit densities, the rule exhibits particle dynamic phenomena, as might be seen in a rarefied gas. At high bit densities, however, it acts like a dense gas, and defects or particles executing apparently random walks can be seen.

[ Table 4.1 ] Block transitions which define the , rule which reproduces the diffusion equation. Blocks which change under the rule are shown in bold. The rule is applied on alternate time steps to even and odd blocks in the one-dimensional cellular automaton configuration. The rule is arranged to be reversible, so that each block has a unique predecessor as well as a unique successor under the time evolution. It is also bit conserving, so that the total number of binary bits in each block is invariant under these transitions.

The microscopic configurations of this system are highly sensitive to small changes in initial conditions. Figure 4.5 shows the pattern of differences associated with the change in single initial site value. The pattern of differences is seen to expand at a fixed ``speed of sound''.

The overall average behaviour of this system however obeys the diffusion equation, and so is insensitive to small changes. This phenomenon is just the same as occurs in real gases.

The cellular automaton of table 4.1 can be considered as a system which contains particles executing random walks. What is perhaps remarkable about it is that the randomness necessary to produce appropriate average behaviour in these walks is generated intrinsically by the system, apparently at a low computational cost.

[ Figure 4.4 ] Microscopic diffusion at two densities in the minimal cellular automaton approximation to the one-dimensional diffusion equation.

[ Figure 4.5 ] Difference pattern for the rule of figure 4.2. This shows the bits which change as a result of a change in a single initial bit in a random initial configuration.

One can consider this system as a random sequence generator. The effectiveness of the system as a model for diffusion is related to its effectiveness as a random sequence generator.

One issue is what the global behaviour of the system on a finite lattice is. Since the system is reversible, all states lie on cycles. Table 4.2 gives the multiplicities and sizes of these cycles for various lattice sizes.

The lattice sizes so far investigated are not large enough to determine whether the maximum cycle time for the system does indeed increase exponentially with its size.

The exact sets of cycles that occur for particular lattice sizes depend on the number-theoretical properties of the lattice size. It is clear that the system is not ergodic, since there are often many distinct cycles. Some of these cycles may however be largely spurious. For example, when the lattice size is not prime, there are classes of initial states whose site values show a periodicity which is some divisor of the lattice size. Such classes of states must lie on distinct cycles.

For complete randomization to occur, the system should have no conservation laws other than that of total bit number. The presence of multiple cycles implies that some other conservation laws may exist. However, no simple invariant quantities seem likely to be associated with these additional conservation laws.

[ Table 4.2 ] Cycles in finite size systems evolving according to the rule of table 4.1. In each case, the cellular automaton is taken to have periodic boundary conditions. The multiplicities and sizes of all cycles are given. For width 11, the cycles have lengths which contain all primes up to 149, excluding 101, 107, 113, 127 and 131. An ergodic system would have just one cycle.

previous  l  next