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. As part of the general background for the commentary, we still need to describe the uniform multiplicity theorem.
To summarize what has been discussed so far:
1) There is a diagram, actually at least a century old, which gained much prominence in shift-register theory, called the de Bruijn diagram, which manages to subsume a great deal of the theory of linear cellular automata (and is a starting point for higher dimensions). That is, provided that it is labelled appropriately and interpreted satisfactorily.
This diagram just tells how to connect Wuensche and Lesser's 'start strings' together, and is practically a recipe for playing dominoes, which is another profitable way to interpret cellular automata --- as a tiling problem.
2) For purposes of calculating ancestors, the de Bruijn diagram, or more appropriately, its connectivity matrix, has to be split into two parts. (For a binary automaton, that is, which is what is being discussed.) If symbols are put in the right places, and the symbolism of regular expressions is used, multiplying the matrices yields explicit ancestors. The practice would be more useful than it is if the complexity of the expressions did not grow exponentially. But that is the nature of reality, and decimal notation for numbers hides the fact that the size of products indeed grows exponentially. Moreover, in performing arithmetic, products and sums are consolidated into single numbers at each stage, whereas simplifying symbolic expressions as you go along never helps much.
For the purposes of counting, numerical de Bruijn fragments are quite satisfactory, but the problem remains of working with (noncommutative) matrices rather than numbers, affording a good chance for using ones numerical knowledge about matrices, and especially about non-negative matrices.
3) From the de Bruijn diagram, two more diagrams can be constructed, each of which illuminates the theory in its own way. The first is the subset diagram, which reveals what kind of paths the underlying diagram contains. It is the same as an exhaustive search, but it prescribes a systematic way to carry out the search. For automata, there are two different diagrams, due to the fact that the start strings can be extended either to the left or to the right. Not all rules of evolution are symmetric by reflection, so the difference is significant.
Applied to the calculation of ancestors, the subset diagram reveals at a glance whether there are ancestors or not. Due to working with subsets, rather comprehensive vision is required for the glance to work; the graph is rather large even for modest automata. Some things are fairly easy to read out of the diagram, but others require work; for configurations which actually have ancestors, it is far easier to multiply the aforementioned matrices than to decipher the subset path.
4) The pair diagram is much more modest than the full subset diagram; with ordered pairs its information is much more explicit. Its principal application lies in detecting and resolving ambiguity. There is a part of the pair diagram in which the two members of the pair are equal, and of course it reproduces the original diagram. However, whenever there is a mapping of the automaton to itself, there are pairs of the form (x,f(x)), whose subset has to show up in the pair diagram. A good example is Wolfram's (2,1) Rule 90, which is the same rule when all the cells are complemented. Both the diagonal and the antidiagonal of the de Bruijn pair diagram match the underlying diagram.
Rule 90 has quite a personality. Amongst other things, the even cells and the odd cells go their own merry ways, quite independently of one another, except for alternating generations.
The opposite of ambiguity is uniqueness, for which the pair diagram also serves. Suppose that the pair diagram has no loops except within its diagonal (pairs of the form (x,x)). Since the complement of the diagonal is finite, any path originating there must exit in fewer steps than there are pairs in the complement (otherwise it would enter one of those disallowed loops); the only place to go is onto the diagonal.
Suppose that a path leaves the diagonal. For the same reason as before, it must either terminate or reenter the diagonal in finitely many steps (again, the size of the complement). If all access to the diagonal is one-way, and if a finite configuration has an ancestor at all, it has to be unique except for a certain amount of leader or trailer. Following up these two quibbles will lead to the type of detailed analysis that we want to dispose of in the most general way, not arguing case by case.
The connection diagram of the pair matrix is also the second moment matrix for counting ancestors. It thereby relates statistics of the automaton, specifically variance in the number of ancestors, to numerical properties of the de Bruijn matrix. Again, general theorems are desired, rather than case-by-case analyses.
It seems to be hard, nay impossible, to get the desired proofs from within matrix theory, which is to say, by deducing limits on eigenvalues or norms (which are growth factors) from the size and arrangement of the matrix elements; this in spite of the fact that the results seem almost ``obvious.''
Rather, the de Bruijn matrices are matrices with positive elements and a norm, which could be, the sum of their elements. As such they form a ring, and rings have ideals, namely an algebraic structure. An ideal is simply a subset which persists under addition and multiplication; there are different kinds of ideals according to the handedness of the multiplication.
These matrices all have different norms, some are bigger, others are smaller. Consider those of minimum norm (which could well be zero). Such matrices are candidates for an ideal. The same for those of maximum norm (which, if it were infinity, would not be very helpful).
Suppose w is a word, N(w) the product of de Bruijn fragments counting its
ancestors, that u
N(w)u is an extremal number (for all finite words),
and that a is a single cell which we will add to the chain. N(wa)=N(w)N(a)
is the new ancestor matrix. NOW, average over all the one-cell extensions;
we have to divide by 2 (the number of states, 2 for binary automata) to get
1/2(N(w)N(0)+N(w)N(1)). N(0) is the earlier A matrix, N(1) the B matrix.
Taking out a common factor we get 1/2N(w)D, because D is the sum of the
de Bruijn fragments. We need 1/2(u
N(w)Du), but Du=2u!. So we have
u
N(w)u back, which is still that extremal value. HOW can an AVERAGE
be EXTREMAL? Only if everything being averaged is equal, and we see that
the value is the same for all long chains.
Cleaning up details (the upper bound is actually finite, making it equal to the lower bound, therefore not zero and equal to the value for even single cells) we finally have the Uniform Multiplicity Theorem: Unless every configuration has the same number of ancestors as every other, there must be some configurations without any ancestors at all.
This soup is still not free of flies; how is it possible for there to be unique ancestors, and hence reversible automata, if all the configurations have to have four ancestors (the average is 4, so zero-variance means that all are 4) to avoid that one of them has none?
More commentary will follow.