From: McIntosh Harold V.-UAP (mcintosh@redvax1.dgsca.unam.mx)
Date: Mon Jun 21 1993 - 16:49:30 UTC
Last fall and this spring various discussions have taken place regarding Andrew Wuensche (<100020.2727@COMPUSERVE.COM>) and Mike Lesser's new book, 'The Global Dynamics of Cellular Automata.' Not having had a copy of the book to refer to has precluded making any commentary on its subject matter, but a copy has now arrived in Puebla (Puebla has a splendid Colonial Cathedral, is near to a World-Famous Pyramid (Cholula), but you will look in vain to find a University Bookstore). To begin with, the book is a real work of art, with something like 200 pages of carefully drawn evolution diagrams, for binary rules with 3 and 5 neighbors. All the symmetry classes of the former, and mostly the totalistic rules of the latter are shown, for rings of up to 15 cells. All in all, a tremendous collection of data, a vastly expanded version of Holly Peck's Table 13 in Wolfram's 'Theory and Applications of Cellular Automata.' There is no telling how often, or how many people, have thumbed through that appendix, looking for examples of something or other. Just as many delicacies serve as appetizers, not constituting the whole meal, this valuable collection may serve more to whet our interest, while it satisfies our curiousty, than to offer us the Final Word. But then, noone wants to propose that someone publish a 10,000 page atlas, just to keep our interest going! One of the first things which come to mind are the theories of random graphs of Erdos, Bollobas and others. Evolution diagrams are trees rooted on cycles, so we know beforehand that there will be connected components (the different cycles) and no loops otherwise. We also know that the graphs must have the symmetry of the ring, so that there will be cyclical and reflective repetition of structures. Within those constraints, the statistics which can describe the graphs are: average branching ratio, average length of transients, maximum and minumum values of these two quantities, and their variances. According to random graph theory, links should distribute fairly uniformly over the nodes (insofar as constraints allow, and one constraint is --- one and only one out-link per node). More than that, the distribution is Poisson-like, so that the actual number of links is rarely the exact average, but nearby according to the well-known formula. As a first reaction, based on my own experience, it might be interesting to comment on a study of (2,1) Rule 22, which is a sort of one-dimensional version of Life, which we made several years ago. Somehow, it did not seem that the rings became interesting until their circumference reached 20; from that point on several alternative structures showed up having the same period, and structures began to have a greater variety in general. Indeed, it was at this point, with the help of several incisive observations on the part or Robert Wainright, that we discovered how de Bruijn diagrams could be used to deduce the possible periodic configutrations of a one-dimensional automaton. We carried out a complete analysis of cycles up to rings of circumference 34. Two things happened; first, 2^34 is 16 billion, and the analysis took months on two or three microcomputers running in parallel (2MHz 8080's). So adding another cell would have taken twice as long still. But vestiges of a second phenomonon began to appear; for shorter rings, periods in the tens, maybe hundreds showed up. But at n=34, periods began to run in the thousands and beyond. That could be confirmed, because certain configurations for Rule 22 are very regular, and could be checked explicitly. In fact, one suspected that a further great jump might be waiting at N=66, and at related values thereafter. Actually, the literature contains some other instances where rather extensive results are available, namely for rules like the exclusive or's (which are equivalent to finite fields), where matrix theory gives pretty complete results. What this means with respect to the Atlas, is that in spite of the wealth of data which it contains, it may just be skimming the surface of a large reservoir of interesting automata. The foregoing comments suggest that it may be fairly adventurous to extrapolate from small rings; but if one is forewarned, the small rings can still be used to good advantage. The Atlas contains much more than just the evolutionary diagrams; one of its most valuable features may be the comparisons which it suggests, and documents to a good extent, between automata whose rules are similar. One always suspects that similar rules should produce similar automata. Lenore Levine, Regular Language Invariance under One-Dimensional Cellular Automaton Rules, Complex Systems 6 163-178 (1992) has described an interesting sequence of rules, which deviate less and less from Rule 128 - OR, from a topological point of view. With the programs which accompany the Atlas, such ideas can be tried out, and their results evaluated. More commentary will follow. 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:16 UTC