NetNews Usenet Archive 1992 #27/NN_1992_27.iso/spool/comp/theory/cellaut/547

Text File | 1992-11-21 | 5.6 KB | 101 lines

Newsgroups: comp.theory.cell-automata
Path: sparky!uunet!europa.asd.contel.com!emory!gatech!bloom-beacon!INTERNET!dont-send-mail-to-path-lines
From: [e-mail] ("Harold V. McIntosh")
Subject: Basins of attraction.
Message-ID: <[e-mail]>
X-Unparsable-Date: Fri, 20 Nov 92 23: 54:07 MEX
Sender: [e-mail] (Wizard A. Root)
Organization: The Internet
Distribution: inet
Date: Sat, 21 Nov 1992 07:13:12 GMT
Lines: 88

Thanks to Andrew Wuensche <100020.2727(at)COMPUSERVE.COM> for answers to
my commentary. A full response will take time, but here is a first reaction.
The scheme of running down a line of cells, building up a tree of ancestors
is one that we have probably all played with. but some people have formalized
it better than others, and some people have evidently worked out consequences
in more detail than others.
-
Erica Jen likes to work with recursion relations whereas some of us get on
better with matrices. Nevertheless she, and perhaps Stephen Wolfram earlier,
and maybe still others have found that there is a nice symbolic-numerical
calculus that is based on de Bruijn matrices, wherein there is a matrix
standing for each state in the automaton. Multiplying out a row of symbolic
matrices gives you all the ancestors of that sequence; using numerical
matrices gives you numbers of ancestors instead.
-
The fact that matrices are involved instead of just ordinary numbers (or
a single line of symbols) is due to the fact that the ancestor row is longer
than the child row, so you get some liberty of choosing the margins, just as
Wuensche's message describes. You can define sort of a metric for these
matrices: If you look at all elements you get unrestricted ancestors, looking
at the diagonal elements (trace) gives periodic configurations (left margin
has to match right margin), while looking at the (0,0) element gives you
configurations quiescent at infinity.
-
There are some nice variants here. Jen's scaling rule falls rather nicely
out of this formalism. Symmetric rules (Escher rules) such as the ones that
Torben AEgidius Mogensen <torbenm(at)DIKU.DK> works with can have a nighttime
at left infinity and a daytime at right infinity. Wolfram has suggested that
twisted boundary conditions might have some merit. And so on ...
-
A Garden of Eden in these schemes is indicated whenever the appropriate
projection on product matrices vanishes. Some people (I don't have a reference
at hand) have approached this through rings of integer matrices. Vanishing
implies certain ideals; the trick is to get the ideals without doing the
arithmetic, if that is possible.
-
The classical approach to the Garden of Eden is through Moore's subset
diagram; the trouble with that is that it detects Gardens of Eden, and
gives you a very explicit language of 'poison words' (The Garden, of course,
has its Serpent). However, a link in the subset diagram just says that SOME
node in the source subset is linked to SOME node in the target subset (with
a guarantee that every node in the target has at least one in-link), so it
is rather hard to read off the ancestors, when they do exist. That is where
the de Bruijn matrices offer a better approach.
-
One detail about the subset diagram is that if there is NO path leading from
the full subset to the empty set, then there is a rather interesting structure
of minimal subsets reachable from the full set (as well as maximal subsets
connected to the empty set). This appears in Hedlund's work, and allows him
to define an 'index.' There are in fact left indices and right indices; this
is due to the fact that there are really two subset diagrams, according to
whether the initial neighborhood is extended to the left or to the right
(What do you do in two dimensions?).
-
It is my feeling that this situation lies behind the observation:
>
>    One-way limited pre-image rules (either left or right, not both)
> must have pre-imaging less than the theoretical maximum of 2^(n-1), for
> example n=3 rules 30 and 45 (the proof is given in my the book). These
> rules result in many states having only one pre-image (balanced?),
> and thus their basins of attraction tend to have very long transients
> and attractor cycles, corresponding to chaotic behaviour.
>
But it will be necessary to look this over more carefully before being sure.
Rule 30, of course, has a very interesting personality.
-
Anyway, to turn to questions of variance --- The numerical form of the
de Bruijn matrices mentioned can be used to calculate statistics about the
ancestor variance. If sums of tensor powers of these matrices are formed,
their traces (or other appropriate projections) give the moments of the
distribution. Or rather, they give the moment-per-unit-length of the
ancestors, so their maximum eigenvalues are what govern the statistics
for very long configurations.
-
Zero variance means that ALL configurations (from one cell to infinity) have
the same number of ancestors. It seems hard to reconcile this with the fact
that reversible automata have just ONE ancestor, but the answer lies in the
observation that we get to play with the margins. The essential theorems (and
this is what keeps the theory from being completely trivial) state that in
the limit, THE MARGINS DON'T MATTER. Proving this is presumably part of what
ruins the nice theory for two dimensions and above, requiring something like
Moore's 'erasable configurations' to get a proof. It also opens the door to
topology, by giving a meaning to 'in the limit.'
-
Harold V. McIntosh             |Depto. de Aplicaci'on de Microcomputadoras
[e-mail]        |Instituto de Ciencias/UAP
[e-mail] |Apdo. Postal 461
(+52+22)43-6330                |72000 Puebla, Pue., MEXICO