new books and old articles (13)
In the process of preparing the way for more abstruse theories of equivalence, perhaps it is possible to lose sight of some of their simpler aspects. The general definition is that two systems are equivalent if they work the same way both before and after the first has been mapped into the second.
When the working is described by a matrix, such as the sequence matrix in subshifts of finite type or the de Bruijn matrix for the evolutiuon of an automaton, and the mapping is characterized by another matrix, the algebraic formulation of the requirement is that A X = X B, with A and B as system matrices mapped by X. If X is invertible, the equation can be rewritten in a more familiar form. If the relationship can not so easily be described by matrices, then rewrite the equation by composing more abstract functions, creating one of category theory's commutative diagrams.
Some sleight of hand reveals one possible origin of such an equivalence, namely that A and B have a mutual factorization wherein A = P Q and B = Q P, for some pair of matrices P and Q. Just this situation has turned up in one of the books under review, wherein the (2,1) automaton Rule 18 is a composite of (2,1/2) rules XOR and OR, whilst Rule 252 is the same composite in reverse order. This is yet another variant on the Ito relation, wherein (126) (252) = (252)(18), although these are but two of a multitude of transformations serving to relate the two rules.
That such an intensely studied rule as Number 18 has factors is not so mysterious; that's the rule that turned up when the automaton was built that way. Although the OR-XOR combination has been used in several contexts, with the intention that the OR proliferate live cells (ones in a field of zeroes) following which the XOR curtails them, leaving only boundaries.
For (2,1) automata, there is an interesting effect, which is built up by observing several details of the de Bruijn diagram. There are only two links labelled "1" in the diagram, and they connect two different connected subgraphs which generate only zeroes. One of them is the self-loop centered on a pair of zeroes, reflecting the rule's quiescence. The other has a loop centered on a pair of ones, but it can never be used after the initial generation because the diagram admits at most two ones in sequence. That leaves a subgraph generating zeroes which can only create an even number of zeroes, possibly by destroying an isolated pair of ones.
The only way a pair of ones can arise is for a string with an even number of zeroes to shrink by two cells each generation until all are gone; if that interval itself was generated by cancelling ones rather than by shrinking a longer interval, only one of whatever pairs were originally present will seem to survive. Thus "kinks" (parity shifts in the cummulative length of gaps) will annihilate in pairs at the tops of the large inverted vacant triangles so typical of the evolution of binary automata, with a frequency which depends on the likelihood of forming such triangles. Peter Grassberger published many results on the statistical properties of this particular automaton, beginning for example with
P. Grassberger "Chaos and Diffusion in Deterministic Cellular Automata," Physica 10 D 52-58 (1984),whose mechanism was elucidated and generalized by Erica Jen
Erica Jen, "Aperiodicity in One-Dimensional Cellular Automata," Physica D 45 3-18 (1990).Even at the time of the first Cellular Automaton Conference, Douglas Lind described the relation of Rule 18 to a Sofic System in
D. A. Lind, "Application of Ergodic Theory and Sofic Systems to Cellular Automata," Physica 10 D 36-44 (1984),although being able to do so required some knowledge of the actual workings of the automaton, just as did Jen's analysis.
In the last installment, the formations of membranes was mentioned. A good account of this and the usage of de Bruijn diagrams in greneral can be found in the article:
Erica Jen, "Invariant Strings and Pattern-Recognizing Properties of One-Dimensional Cellular Automata," Journal of Statistical Physics 43 243-265 (1986).There have been innumerable efforts to interrelate the properties of automata, often with the intention of finding a member of a class which is in some sense "soluble," from which to extrapolate the other members. These attempts include finding simple transformations as well as trying to work up a perturbation theory, according to which automata with similar rules will evolve similarly. Perturbation works best when it conserves as much as possible of the loop structure of the de Bruijn diagram, failing more severely according to the number of cycles which are broken.
Concentrating more on generalities than on particular mechanisms, the principal characteristic of cellular automata is their basins of attraction, which is to say, the behavior which they exhibit after a long time, and the route by which that becomes the preferred mode of operation. Basins of attraction depend for the most part on the distribution of ancestors for single-generation evolution, configurations with many ancestors being the most likely to become attractors.
The number of ancestors is something which can be estimated from the de Bruijn fragments, mainly by looking at the comparitive eigenvalues of products of the de Bruijn fragments. What is worse, to first approximation, these eigenvalues are fairly well determined by the counterimage imbalance in the automaton's neighborhood, which is to say, by Langton's parameter.
What seems to have been overlooked in our previous discussions of this subject is the applicability of Hedlund's third great theorem, even for mappings which are not surjective. Generally speaking, if the mapping f has a certain multiplicity, and g has another, the composite fg ought to have the product of the two multiplicities. For surjective mappings, the multiplicity is uniform making the Welch indices truly multiplicative, and even guaranteeing that both fg and gf have the same multiplicities. Likewise for the equivalence fh = hg, it would follow that f and g would have the same multiplicity, at least with nonzero h.
Combinatorially, things don't work out too exactly, as may be seen from the way Rule 18 factors. The boolean function OR has the forbidden word 010, but XOR has none. Rule 252 excludes 010 because the second mapping couldn't make this sequence, no matter what the first mapping may have done. The other way around Rule 18 has the forbidden word 111 (amongst others); although OR's immediate deficiencies might have been compensated, new ones seem to arise. Necessarily so, because one of Hedlund's results is that if a composite mapping is surjective, the same must be true of the factors, something at which OR fails.
Note that the common sense result would allow the second mapping to heal deficiencies in the first, which means that either the special environment of cellular automata or the topological properties of a continuous mapping of a shift conspire to prove the theorem. In either event, the strong result exists that if a composite is surjective, so are the factors; we need something weaker for merely continuous maps.
One intermediate possibility is to look at the composite of a surjective map with its uniform multiplicity and a merely continuous map, with its spectrun of multiplicities. Checking on (2,1) Rule 18, for example, and coaxing the T-matrices involved a little bit, yields estimates for the top eigenvalues of the T-matrices for Rule 18 and the (2,1/2) OR which are close enoough to suggest a relationship.
Does anyone happen to recall the rule for compounding variances for composite distributions?
Somehow trying to explain a result by both topology and combinatorics seems to end up without an explanation from either end. Combinatorially, the basic result is not exactly the uniform multiplicity theorem; instead it is the process by which the theorem is proven, namely once having counted out all possibilities, remarking that an average cannot surpass a maximum replaces the usual cardinality argument for finite sets.
Hedlund's topological proof depends somehow upon the conservation of closed sets by continuous mappings, so that if the image of a subset is the whole space, it had better have been the whole subspace in the first place. Working that out with deltas and epsilons ought to bring us back to the combinatorial line of argument.
In the end, considering multiplicity as a multiplicative factor characterizing an automaton rule, we find that it only works with precision when multiplicity is uniform. When the rule is not surjective, the example of Rule 18 (or, in another context, the Chaté-Manneville rules) shows that the dynamics can be much more complicated, as when ease of production of favorite configurations promptly eats up all the raw material from which they arise.
Continuing to speculate on the temporal versus spatial proliferation of ancestors, observe that since the subset matrix has a constant row-sum, the number of ancestorless configurations multiplies by the state sum with each length increment, so an interesting quantity has to be the ultimate percentage of orphans. This ratio is first established for short configurations, where new exclusions are more numerous than continuations of old exclusions, in a way entirely consistent with the observation that the periodic repetitions of shorter configurations generate the larger basins of attraction.
To summarize, now that we have some new tables of data, and another point of view (commutation and composition relations among rules), as expressed in the book we were reviewing, there seems to be motivation to go back and reexamine some of these older results, especially in the context provided by having studied Hedlund's ideas more carefully than they otherwise may have been. On the other hand. to complete this series, we need to examine the subshifts in more detail.
-
Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx