reversible 1-d CA?

[McIntosh Harold V.-UAP]

wim...@sci.kun.nl (Wim van Dam) asks:

> I'm looking for some: two-state, one-dimensional, reversible CA-rules, which
> (nevertheless) produce non-trivial behaviour.

Non-trivial lies somewhat in the eye (or mind) of the beholder. Probably the
first publication along these lines was the article of Amoroso and Patt in
1972, wherein they found by exhaustive search some (3,3/2) [four-neighbor]
reversible automata, and announced a general construction, something
involving an xor of a chain of states, to get a whole family of reversibles.

Somewhat later Fredkin conceived of a scheme for reversing automata (several,
in fact, but one of them was still confined to one dimension), but since it is
equivalent to using a cartesian product, the least you can get is a four-state
automaton.

Now and then searches have turned up other reversible 1-D automata, and the
topic comes up for discussion on CA-Mail fairly frequently. Now and then
articles devoted to the subject have been published, one of the most
comprehensive of which was authored by David Hillman; namely, "The structure
of reversible one-dimensional celluolar automata," Physica D 52 277-292 (1991).
He cites well-known transformation rules to reduce automata to radius-1/2
[two-neighbor] equivalents, invokes some further equivalences, and finally
announces a search scheme which will yield up all the reversible automata.

The question of reversible automata is tied into the theory of symbolic
dynamical systems, which is sometimes invoked in treatments of automata
theory. In that area, a paper of R. F. Williams, "Classification of subshifts
of finite type," Annals of Mathematics 98 120-153 (1973), is often mentioned,
along with the fundamental paper of G. A. Hedlund. The relationship is rather
specialized, and seems to require a certain amount of preparation and training
to follow it through.

Following what seems to be the relationship requires going back to the Atlas
of Wuensche and Lesser, in which they catalog the basins of attraction for
all the (2,1) automata and show examples for cycles up around 15 cells in
length. An algebraic, or at least matrix theoretical, approach to these basins
can be gotten from the A and B matrices, the connectivity matrices of the
de Bruijn diagrams of their automata. Matrix elements of products of those
matrices tell how many ancestors their corresponding configurations have, and
thus define the branching found in the trees of the basins of attraction.

For reversible rules, there can be no branching, and the basins are required
to consist of pure cycles. But there is a symmetry situation, in that
permuting the labels of the states of the automaton obviously can't affect
their reversibility, nor can forming Wuensche and Lesser's clusters. The
result is huge clusters, but Hillman seems to have found that there aren't
very many distinct clusters. This has some bearing on what one calls
"non-trivial."

According to Williams, equivalence between shift systems (which would make
one of them reverse the other) depends on certain relations between the
connection matrices defining the shift, essentially these selfsame A and B
matrices. There are in fact three levels of relationships.

1) "topological conjugancy" suppose that M and N are connection matrices,
and that there exists a matrix R, possibly rectangular, for which RM = NR.
That means that R defines a mapping between nodes, which conserves links in
the (directed) graphs (of possibly different sizes) whose connections are
given by M and N. In addition there may be a matrix S (say, R transposed)
for which MS = SN, so that conservation of linkages goes both ways.

2) "strong shift equivalence" suppose as before that M and N are connection
matrices, but that they derive from a factorization in which M = PQ and
N = QP. Rather than saying that their graphs have image links connecting
image nodes, the two graphs are duals of one another. At least, that is the
case in the particular situation where P and Q define either functions or
antifunctions, and may be considered as a sort of generalized duality.

Simple algebraic manipulation shows that MP = PN and that QM = NQ (without
saying that P and Q are transposes).

3) "weak shift equivalence" Williams finds a modified requirement, merely
that there be a common power k for which M^k = PQ and N^k = QP, to obtain
shift equivalence in the shift dynamical system. The origin of this alteration
seems to lie in the fact that a connection matrix is a secondary consideration
for dynamical systems, and that a shift of length k may be required to
synchronize one system with another.

In any event, what has to be understood are the possible equivalences between
matrices with integer coefficients, or even the more restricted classes where
the integers must be either positive, or non-negative. Over the complex field
these relationships are easily satisfied, by appealing to the Jordan Normal
Form.

If m = u l v, where we use upper and lower case for the members of the pair,
and l is diagonal with uv = vu = (identity matrix) (life complicates with
Jordan blocks, but much is to be learned before introducing them), and
M = U L V, with UV = VU = (Identity Matrix). then candidates for r and s are
r = Uxv and s = uYV, where x any y are appropriate diagonal matrices.

One fundamental reality, whatever the field, is that PQ and QP have to have
common eigenvalues and related eigenvectors, with the exception of discrepancies
with eigenvalue zero. The same is true of topological conjugates, so if M and
N do not have common eigenvalues, P and/or Q must annihilate some vectors.

A consequence is that one should only aspire to construct a topological
conjugacy when the topological matrices have the same Perron eigenvalue
(the real eigenvalue of strictly maximum modulus which is the common heritage
of all non-negative matrices). Actually, any common eigenvalue would do, but
the Perron eigenvalue comes with a real (rational, for rational matrices)
positive eigenvector, nice if the mapping is supposed to be a function
between point sets.

The matrices x any Y can be manipulated to make r f(m) r = f(M) r, giving
weak [f(m) = m^k] and strong [f(m) = m] equivalence under circumstances which
look suspiciously like requiring m and M to have eigenvalues which are either
zeroes or ones. If that were true, than the A and B matrices mentioned above
would have to share this property, and it would greatly simplify searching out
reversible pairs of cellular automata.