Table 6: Statistical Properties

Statistical properties of evolution from disordered states.

Results are given for all the ''minimal representative'' rules of table 1. In all cases, initial configurations were used in which each site has value 0 or 1 with probability . Some properties of some rules remain unchanged with different kinds of initial configurations.

Rational numbers, or numbers without errors, are quoted whenever analytical arguments yield exact results. In a few cases, the rigour of these arguments may be subject to question.

The column labelled ''density'' gives the asymptotic density of nonzero sites. For some, but not all, rules this depends on the initial density, here taken to be . For most rules, the relaxation to the final density appears to be approximately exponential. For some rules (such as 18), in which particle-like excitations undergo random annihilation, the relaxation may be like , or slower. Rule 110 shows particularly slow relaxation.

The column labelled gives estimates for the asymptotic spatial measure entropy, as defined in pages 115--157 in this book. This quantity gives a measure of the ''information content'' of cellular automaton configurations. It is computed by breaking the configuration into blocks of sites, say of length , then evaluating the quantity , where the sum runs over all possible blocks, which are taken to occur with probabilities . is the limit of this quantity as . The values decrease monotonically with , allowing upper bounds on the limit to be derived from finite results. Where errors are quoted, the values or bounds on given in the table were obtained after 400 time steps, with blocks up to length considered. (More accurate results were obtained for rules 22 and 54.) Fits to values obtained as a function of suggest that the exact for rules 22 and 54 may in fact be zero.

The definition of implies that it achieves its maximal value of 1 only when all possible sequences of site values occur with equal probability, so that each site has value 0 or 1 with independent probability . if only a finite number of complete cellular automaton configurations can occur.

Results for given without errors in the table were obtained by explicit construction of probabilistic regular languages which represent the sets of configurations produced by cellular automaton evolution, as in table 11.

The quantities and are left and right Lyapunov exponents, which measure the rate of information transmission. They give the slopes of the left and right boundaries of the difference patterns illustrated in table 4. Thus they measure the rate at which perturbations in cellular automaton configurations spread to the left and right.

The notation --- indicates that almost all changes in initial configurations die out, so that the are not defined.

The notation indicates that the information propagation direction can alternate, typically as progressively more distant particle-like structures from the initial configuration are encountered. There is probably no definite infinite size limit for the in such cases.

Rule 110 shows highly complex information transmission properties, associated with the particle-like structures of table 15. The values of given in the table for this case are possible bounds associated with the fastest and slowest-moving particle-like structures.

The quantity is the temporal measure entropy, which measures the information content of time sequences of values of individual sites. It is evaluated by applying the same procedure as for but to sequences of values of a single site attained on many successive time steps. It can be shown (see pages 115--157 in this book) that .

The quantities and measure respectively the information content of spatial and temporal sequences that are one site wide. The quantity gives the entropy associated with spacetime patches of sites of arbitrary width. (Nevertheless, for many rules, the exact value of is in fact obtained from patches of width 1 or 2.) In general, , and .

The quantity is evaluated by considering spacetime patches of sites that extend in the time direction. The last column of the table uses a generalization in which the patches can extend in any spacetime direction. It gives the minimum value obtained as a function of direction. (The actual bounds given in the table were obtained from vertical or diagonal patches; other directions may yield stricter bounds.)

Table by Peter Grassberger (Physics Department, University of Wuppertal).

previous  l  next