From: McIntosh Harold V.-UAP (mcintosh@redvax1.dgsca.unam.mx)
Date: Wed Jul 14 1993 - 01:18:34 UTC
Commentary related to Andrew Wuensche and Mike Lesser's book, 'The Global Dynamics of Cellular Automata.' Addison-Wesley, 1992 (ISBN 0-201-55740-1) concludes. Having made an extensive analysis of the role the average number of ancestors (Langton's parameter lambda) plays in classifying and describing cellular automata, some attention needs to be given to Z, a new parameter which the authors have introduced. We have based our own analysis on a theory of graphs, specifically, the de Bruijn diagram of the automaton, from which ancestors and their properties can be readily calculated. Langton's lambda, which is gamma in the formula below, plays a prominent role in this analysis because it represents, within about ten percent, the quantities needed to derive the statistics of the automaton. First, the rate of growth, with length, of the number of ancestors of that string of cells having the greatest number of ancestors. Second, the rate of growth, with length, of the standard deviation in the number of ancestors of whatsoever string of cells. From then on, the higher moments are simple polynomials with respect to the same parameter; to the extent that it is feasible to turn moments into frequencies, they provide the data which is required. Implicit in this point of view is the assumption that the eigenvalues of selected graphs are the real parameters which ought to be used, but that there are certain advantages to using an easily calculated approximation to them, especially if the same approximation is relevant to all the graphs. It would seem that the concept of Z arose in the attempt to refine lambda, given that a ten percent approximation is not always sufficient, and that there were observable differences in the behavior of automata having the same value of lambda. Z itself is subject to refinement, as is explained with some care on pages 40, following, in the Atlas. In the formula below, only the first approzimation to Z is used. As the layout of the Atlas demonstrates, Z does in fact refine the classification of the automata depicted. The formulae in question define the eigenvalue of the larger de Bruijn fragment (which is our parameter of preference) in terms of the other two: (Langton) lambda = gamma + n sigma(c) sigma(x) cos(theta) (W & L) lambda = 1 + 2n sqrt(1-Z) sqrt(0.5*s^2 + .01561) cos(theta*) The Langton version simply takes the fraction of ancestors and discards the correction; the nature of the correction for many rule clusters was tabulated in the previous commentary. The W&L version could be tabulated similarly, but suffice it to say that the new quantity theta* (always less than 90 degrees because 1 is always an underestimate) ranges over the whole quadrant. In contrast the W&L version (which is our own invention; the Atlas does not mention such a thing) takes 1 as the basic growth factor, and augments it according to Z and a multiplier which would have to be calculated in each instance. Unfortunately it does not seem to be possible to give a single, constant, empirical estimate for the factor, and procede from there. Let us emphasize that W&L themselves never ever intimated that such a thing should be expected; we are only describing our own attempts to relate their theory to ours. If we agree that the growth rates mentioned, however it is that they are estimated or calculated, are the underlying parameters, we can conclude our commentary with some further general observations. Although the following phenomon can occur at any level, it is most noticeable for balanced or nearly balanced rules. In previous commentary, the AB = 44 Rule 29 had A and B matrices with maximum eigenvalue 1, yet this Rule is not one of zero variance. The explanation is implicit in the spectral norm of these matrices, the square root of the largest eigenvalue of their product by their transpose. The spectral norm refers to the largest growth factor for any multiplier of this matrix (which need not be a composite of A and B products); it turns out that both AB and BA have larger maximal eigenvalues than either A and B (although their norms cannot be larger than the product of norms of their factors). The consequence, which is readily apparent from consulting the Atlas, is that neither strings of 1's nor strings of 0's have ancestors which increase in number as the length of the strings increase. However, AB generates strings in which 01 alternate, and these are observed to be strings with maximal preimaging. Can it happen that A, B, AB, and BA have maximal eigenvalue 1, and yet ABB (for example) has a larger eigenvalue? We are not prepared to say. An earlier commentary contained a histogram for ancestor multiplicity in (2,1) Rule 22 strings of length 8. Examination of page 96 of the Atlas allows us to try out the histogram, although the detail for length 13 is easier to read than the drawings for length 8. There is indeed a variety of in-degrees, although we would not be willing to say that the sample is large enough to draw any conclusions. It is an interesting question as to whether we have any right to apply the conclusions taken from the de Bruijn diagram for a single generation of evolution to the higher levels of the trees shown in the Atlas. Ancestors of ancestors should be no more free of correlations than descendendants of descendants, and probably a great deal harder to detect if correlation is to be discovered in the branches of counterimage trees. We could either construct multiple-generation de Bruijn diagrams, or simply assume that the correlation is not all that important, which is often a fair assumption. A respectable portion of the Atlas is devoted to totalistic (2,2) Rules. We do not have much to say about this except to note that experience indicates that totalistic Rules are very atypical; for example, they appear to harbor an undue percentage of Class IV Rules. Nevertheless, the general precepts of graph theory which we have outlined apply to all automata Rules, and it is only the extremely large numbers of automata in categories beyond (2,1) that precludes working them all out, or including them in an Atlas such as this one. The last few pages of the Atlas contain what may be one of its most interesting offerings, the visualization of the effect of mutations on basins of attraction. This is also an area which is amenable to treatment by graph theory, and especially matrix theory. Unfortunately, the perturbation theory which serves so elegantly in quantum mechanics, depends very strongly on working with hermitean (or symmetric) matrices, whereas the matrices of graph theory are anything but symmetric (digraph theory, for the purists). There are still general theorems, such as those asserting that any increase or decrease in one single matrix element is immediately reflected by the corresponding modification of the maximum eigenvalue. Since the connectivity of the de Bruijn fragment has an important bearing on all subsequent analysis, it follows that those mutations which alter connectivity will have a more drastic effect than those which merely change the number of existing connections. By the same token it is much easier to either calculate or just estimate the effect of mutations which preserve the overall connectivity. In concluding, perhaps a comment ought to be made which is not scientific, but rather has to do with prevailing attitutes towards programs and computing. The Atlas contains a program suitable for IBM PC's and clones, by which the results contained in the Atlas may be reproduced and extended. This is indeed a valuable feature of the Atlas, and allows its owner to investigate many more combinations than ever could have been included on a reasonable amount of paper. The authors and/or their Publisher assert a copyright over this program disk, just as they do for the book itself. This is normal practice, and we do not know of anyone who would raise an objection, either to the disk, and especially to the book, being copyrighted. If we understand what we have read correctly, an additional copyright is asserted over any results obtained through the use of the programs which accompany the Atlas. This is not a concept which has gained general acceptance; it is somewhat like claiming that you have copyrighted the cake after having sold the recipe book. Or more accurately, that such protection extends from the cake mixer to the batter to the cake. Computer language compilers have been sold with the claim that the copyright inherent in the compiler program also extends to any code compiled through the use of the program. This is somewhat different from compilers which insert run-time code from a copyright subroutine library. In both cases, many users have preferred to use a product which lacks such encumbrances, rather than endure, or risk enduring, unpleasant complications. It would be a standard element of courtesy to acknowledge the use of any program, such as the one the authors have prepared, in work of one's own; but if this restriction has been understood correctly, a person such as myself would simply write their own program, and be done with it. (We won't talk about the pretensions involved in patenting a program, as that claim has not been made). We sincerely hope that the phrase '... and any images implicit in the software, ...' on page 61 does not carry the dire implications alluded to above. Otherwise, in conclusion, we would like to say that we have greatly enjoyed perusing the Atlas, and that we heartily reccommend it to anyone who wants to have most of the reasonable information about (2,1) and totalistic (2,2) automata readily at hand, where it can be enjoyed in an especially pleasant visual form. The commentary is now finished. Harold V. McIntosh |Depto. de Aplicaci'on de Microcomputadoras mcintosh@redvax1.dgsca.unam.mx |Instituto de Ciencias/UAP mcintosh@redvax1.bitnet |Apdo. Postal 461 (+52+22)43-6330 |72000 Puebla, Pue., MEXICO
This archive was generated by hypermail 2.1.7 : Tue Oct 14 2003 - 21:44:18 UTC