Table 7: Blocking Transformation Equivalences

Equivalences between rules under blocking transformations.

When only particular blocks of site values occur, the evolution of one cellular automaton rule (say ) may be equivalent to that of another (say ). Thus for example, the evolution under rule 1 of configurations consisting of the blocks 000 and 111 is equivalent to evolution under rule 204 in which 000 is replaced by 0, and 111 is replaced by 1. (Two time steps in evolution according to rule 1 are necessary to reproduce one time step of evolution according to rule 204.) Since rule 204 is the identity, this implies that configurations consisting only of the blocks 000 and 111 must be periodic under rule 1 (with period 2).

In general, one may consider replacing site values 0 and 1 in evolution according to rule by blocks and . In some cases, the resulting evolution may correspond to time steps of another rule . Evolution according to rule can thus be ``simulated'' by evolution according to rule , under the blocking transformation , . Such blocking transformations can be considered analogous to block spin transformations in the renormalization group approach.

The table gives possible simulations for all the ``minimal representative'' rules of table 1. The notation : () indicates simulation of rule by replacing 0 with the block , and 1 with ; steps of rule are needed to reproduce one step of rule evolution.

The table includes all simulations for block lengths up to 8. The blocks and are always assumed distinct. Only one representative set of blocks is given for each simulation. (Thus for example, only the blocks 00 and 10 are given for the simulation of rule 90 by rule 18; the blocks 00 and 01 would also suffice.) Simulations with block length 1 are not included; these correspond to transformations given in table 1. No simulations are found for rules 30 and 45 up to block length 8.

Many rules are seen to be equivalent under blocking transformations to simple rules, such as 204 (the identity), 170 (left shift), 240 (right shift), 51 (complementation) and 0. Equivalence is also often found to the additive rules 90 and 150. An important property of all these simple rules is that they simulate themselves under blocking transformations. This has the consequence that patterns generated by these rules are self similar. Fractal patterns are thus produced by evolution according to rules 90 and 150 from single site seeds, as shown in table 5.

The simulations given in the table occur when only particular blocks occur in the configuration of a cellular automaton. In disordered configurations, all possible blocks can occur. But since a cellular automaton under most rules is irreversible, only a subset of blocks may occur after a sufficiently long time. Often the subset of blocks that occur is, at least approximately, the blocks which correspond to a particular simulation. In this case, the behaviour of one cellular automaton may be considered ``attracted'' to that of another.

It is common to find ``domains'' in which only particular blocks occur. Within each such domain, the evolution may correspond to that of a simpler rule. The domains are separated by walls or ``defects'', whose behaviour is not reproduced by the simpler rule. In some cases, the defects remain stationary; in others, they execute random walks, and, for example, annihilate in pairs. In the latter cases, the sizes of domains grow slowly with time.

While a large subset of possible initial configurations for a cellular automaton may be attracted to a particular form of behaviour, there are usually some special initial states (typically occurring among disordered states with probability zero), for which very different behaviour occurs. Such special initial states may for example consist of blocks which yield a simulation to which the rule is not generically attracted.

The blocking transformations considered in the table represent one form of transformation between rules. Many others can also be considered. A general class, which includes the blocking transformations of the table, are those transformations which can be carried out by arbitrary finite state machines.

The blocking transformations used in the table have the property that they reduce the total number of sites. This is a consequence of the fact that the blocks used are always taken not to overlap. An alternative approach is to perform replacements for overlapping blocks, thus obtaining configurations with the same number of sites. An example of such a replacement is , , , . For some rules, the resulting transformed configurations show evolution according to other , cellular automaton rules. Rules related in this way must have the same global properties, and must yield for example the same entropies. The minimal representative rules from table 1 equivalent under such transformations are:

Main table by John Milnor (Institute for Advanced Study). (Original program by S. Wolfram.) Second table by Peter Grassberger.

previous  l  next