Date: Thu, 4 Apr 1996 09:43
To: ca@think.com
The books in question are Voorhees Computational Analysis ... and Nasu's Textiles ... ; the articles are Hedlund's Endomorphisms and Automorphisms ... and Nasu's Local Maps ... . To this list ought to be added R. F. Williams' "Classification of subshifts of finite type ," Annals of Mathematics 98 120-153 (1973) with Errata ibid 99 380-381 (1974).
Having remarked that cellular automata theory embodies two rather separate traditions, perhaps some explanation ought to be given for combining them; but that is easy enough to do --- the theory of the shift dynamical system long ago gave some pretty definite answers to questions which still seem to be somewhat open in automata theory, while in the meantime automata theory has yielded a wealth of empirical information which never seems to have been suspected, let alone contemplated, by the dynamicists. Reviewing books on the subject probably ought to take this into account.
In referring to Hedlund, a considerable amount of topology is encountered. But it is a strange kind of topology, which brings up some interesting doubts about the history of topology; apparently the "Bourbaki" approach dates back to Poincare. That approach is to be distinguished from the delta-and-epsilon methodology which one has learnt from Hardy's "Pure Mathematics," for example.
One of the criticisms of Bourbaki that we used to hear was that it consisted of incredible generalities of which the only known example was the real number system. Well, that just isn't true, and the Shift Dynamical System provides at least one other. The literature provides numerous examples of confusion between the two, both in differential equation theory and in cellular automata theory. That is entirely aside from the fact that the topologists have thought up all kinds of strange limits, periodicity conditions, and pathologies.
To make the point in concrete terms: the real line, even confined to the interval 0-1, depends on real number topology, derived from a metric defined by differences. The topology of sequences depends on the degree to which the sequences agree --- from the beginning for one sided sequences, or in the middle for two-sided sequences. One way to get this is to take the reciprocal of the length of the largest common stretch of agreement as the distance for a metric topology. Sometimes the symbols are taken as integers modulo k, the sequences are treated as k-nary (not decimal) fractions, and the distance is the size of the last significant figure at which agreement occurs. That makes it easy to develop a nice graph.
The formal approach is to give the symbol set the discrete topology and then give sequences the cartesian product topology taken from the symbol sets. This is NOT the real number topology, even though school children are led to think that real numbers are just infinitely long decimals. Salvaging that view is sort of like explaining the easter bunny; in both cases reality is found to be somewhat more complicated than expected.
For real analysis and advanced calculus, mathematicians turn to Dedekind cuts and define real numbers as equivalence classes of finite decimals (rationals), but to practice symbolic dynamics, it is better to keep the sequences and understand that the mapping from sequences (arithmetic without carry) to real numbers (arithmetic with carry) is not as continuous as one would like, and to make the most of it. Thus, two long decimals which are close as sequences are close as real numbers, but some real numbers are close even though their decimal expansions (in the dyadic topology) are not. Exploring this correspondence is usually not undertaken when cuts will suffice, but is necessary if confusion in symbolic dynamics is to be avoided.
In mentioning topologies, or at least distances, it should be mentioned that there is still another which has importance for cellular automata, and that the Hamming distance, which simply counts the number of discrepant terms in two patterns which might otherwise match. Mostly it is used to compare neighborhoods and rule definitions, which are finite in extent, whereas including a divisor which might tend to zero is reserved for such things as configurations, which in principle are infinite.
Turning to the book at hand, Voorhees begins with some sample automata from Wolfram's (2,1) domain (to which the book is primarily devoted), with graphs of their rule of evolution, having previously decided to code configurations as binary numbers. The graphs appear to be perfectly jagged, notwithstanding Hedlund's theorem that these are the continuous shift-commuting functions for symbolic dynamics.
But wait! the discrepancy between the topologies means that the graph has to be much wilder looking to the left than it does looking to the right, and in fact there ought to be a semi-continuity proceeding to the right.
There is a detail which is much harder to see in the graphs of Figures 1.2, which is occasioned by the existence of Garden of Eden configurations, which means that not only are there certain numbers which cannot be values of a given rule of evolution, but they exclude intervals corresponding to numbers where they are an initial segment.
In other places a related diagram can be found, even though it would not be a graph. The plaid diagram, in which Arnol'd's cat map, or Smale's horseshoes can be found, represents the right half of a doubly infinite sequence along the x-axis and the left half, in reverse order, along the y-axis so that the points of the unit square represent configurations. The Shift maps this square in a way which looks anything but continuous until the proper topology is consulted, and clusters of points representing a collection of initial configurations can be followed as the cellular automaton evolves. The plaid arises from observing excluded bands. Unfortunately it would require four dimensions to render the full graph the way Voorhees shows it for semiinfinite configurations.
Naturally one of the reasons for presenting such graphs is to expose their delicate fractal intricacies, something which the figures of the book reveal quite nicely. Graphs have to be carefully drawn and reproduced for all the details to endure close scrutiny; even so, the Garden of Eden, or a lack thereof, does not show up too clearly unless the graph can sustain a rather high degree of magnification.
There is always a question of what to put in a book, and what to leave out. That is why it is nice to have a handy computer program available, to go on beyond the contents of the book. The graphs shown fall in the Wolfram Class III, and IV is missing from (2,1), but ought this to leave Classes I and II without representation? If memory serves, ther have been attempts to Fourier transform, and even Walsh transform, graphs of this nature. But memory does not divulge the results, so maybe someone else knows.
Still, this is just refers to the beginning of the book, still leaveing the main business of this review, namely to compare Hedlund's approach with Wolfram's (to pick two representative names out of a hat) while, at the same time, giving an overview of both the books and the approaches.
To summarize today's discussion --- the topology of cellular automata resembles the topology of the real numbers, but it is finer [close(automata] implies close(real) but not conversely] because it distinguishes sequences that would be considered equal, as real numbers. Bearing this in mind enables an appreciation of fractal graphs and plaid diagrams, and leads to a clearer style of exposition by clearing away whatever uncertainty there might have been that the configurations of automata are somehow real numbers in disguise.