7 views

Skip to first unread message

Feb 24, 1996, 3:00:00 AM2/24/96

to c...@think.com

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.

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu