next up previous
Next: ancestors (11) Up: Ancestors: Commentaries on The Previous: ancestors (9)

ancestors (10)

Commentary related to Andrew Wuensche and Mike Lesser's book, ``The Global Dynamics of Cellular Automata.'' Addison-Wesley, 1992 (ISBN 0-201-55740-1) continues. While referring to this Atlas occasionally, a theory has been elaborated by which the statistical properties of the ancestor distribution for a one-dimensional cellular automaton may be deduced. Presentation of the theory having run its course, interpretation and comparison with the Atlas remains.

The theory which has been presented assigns a prominent role to a quantity which we have called , which is the average of either the row sums or the column sums of a matrix. For the connectivity matrices of de Bruijn matrices, this translates directly into numbers of ancestors, their squares, and their averages. This is reminiscent of earlier work of Christopher Langton, who used such averages for classifying automata; strictly his lambda compared the quiescent state to the rest, but there are only two states for binary automata. Wuensche and Lesser record lambda for all the automata in the Atlas, along with Z, a parameter of their own.

What is new in these commentaries is the relationship between variance and the parameters, namely the rate of growth in the standard deviation which depends upon , where a is the number of ancestors of 0, b the number of ancestors of 1, and 16 is the dimension of the pair connection matrix.

Previously the rate of growth has been tabulated for (2,1) automata; here it is shown for (2,3/2) automata.

In 1972 Amoroso and Pattgif found some non-trivial reversible automata amongst the 614 with zero variance. By non-trivial, one discounts rules which work by shifting, complementing, or copying, which are the only reversible (2,1) Rules.

Another tabulation which we have made concerns (3,1/2) automata; here we have a, b, and c with lambda determined by :

In all of these (three) cases which we have presented, some common features can be observed. Each value of leads to a rather well defined cluster of growth rates, even though the value of itself corresponds to observation better for high values than for low values; nevertheless the discrepancy is gradual and monotonic.

At one time we thought that there was a gap between zero variance and the next lower value, but experience with additional (k,r) combinations has reduced our confidence in its existence; it is most likely an artifact of small sample size (small k, small r). The general shape of the histogram ought to be roughly Gaussian, because of the binomial coefficients associated with given values of , which itself grows quadratically with a. Actually, because of , the purported gaussian is folded over in the middle, ab giving the same data as ba.

Since a Gaussian has a point of inflection at its own standard deviation, we would expect a noticeable division of into low values all of whose Rules have a slow growth rate in their ancestral variance, and those for large growth rates, up in the tail of the Gaussian. It shouldn't be hard to figure out this distribution function, but we haven't done it. What we do notice, is that the growth factor is pretty much the same for quite a few nearly balanced Rules, and that they are set off slightly from the exactly balanced Rules.

With respect to interpreting the Atlas, some additional work is called for. The analysis of variance which we have described ultimately translates into an average number of ancestors per configuration, and the growth of this average with respect to the length of the configuration. The Atlas only tabulates the maximum number of counterimages by basin; but it is the average number which follows more readily from our analysis. The average can be deduced by examining the images, but getting a good sample is going to be laborious.

On the other hand, it is instructive to make comparisons of the maximum number of counterimages, particularly as it depends on the lambda parameter.

More commentary will follow.

next up previous
Next: ancestors (11) Up: Ancestors: Commentaries on The Previous: ancestors (9)

Harold V. McIntosh