From: 100020.2727@CompuServe.COM (Andrew Wuensche)
Subject: basins of attraction
Organization: The Internet
Distribution: inet
Date: Thu, 19 Nov 1992 19:16:28 GMT

re. message from Harold V. McIntosh; 

>Well, I have ordered a copy of the book; delivery has been promised
>for January or February. In the meantime, it is only possible to
>conjecture the contents of the book...

Sorry you have to wait so long. I hope others have found it easier to
get hold of my book !? It came out in the USA in early Oct. 
At the risk of an overlong message, I will try to reply to your
comments, and also indicate the basis of the reverse algorithm.

> ...... and the relationship of the procedures to those
>of E. F. Moore, G. A. Hedlund, M. Nasu, Erica Jen, or even myself.

> 1) Unless the counterimages are balanced, there must be a
>Garden-of-Eden. Presumably this coincides with your 'limited
>pre-image rules' remark above, and immediately foredooms most automata
>to have Gardens of Eden.

> 2) In my early calculations of the variance in the number of
>ancestors, there appeared to be a gap between the rules of
>zero-variance and the others? Have you observed such an effect? Is it
>real (I later decided that it probably wasn't)?

The reverse algorithm for generating pre-images described in my book
[1] relates to Erica Jen's notion of deterministic structures [2]. 
Entries in the rule table, say for 3-neighbour (Wolfram's elementary) 
rules are grouped into pairs of neighbourhoods that differ only by
their rightmost value. If a pair has different outputs, ie

              a1,a2,0 --> T     and     a1,a2,1 --> not T

then given the values of a1,a2 and T, a3 is determined. If all pairs in
the rule table have "left deterministic permutations" as above then
the set of pre-images of any state is easily found by assuming the
start of a candidate pre-image as a1,a2......  Successive values are
determined to the right. As there are 4 assumed starts, the maximum
number of pre-images is 4 for any array size (in general, 2^(n-1) where
n is neighbourhood size). A candidate pre-image can be disqualified if
it fails a periodic boundary condition check.

A pair having the same output is an "ambiguous permutations" ie. 
 
       a1,a2,0 --> T     and     a1,a2,1 -->  T

and implies the "excluded permutations"

       [a1,a2,0 --> not T]   and   [a1,a2,1 --> not T] 

In this case given a1,a2 and T, a3 = 0 or 1 with equal validity
(potentially increacing the number of pre-images); the occurrence of
a1,a2 and not T disqualify the candidate pre-image, potentialy reducing
the number of pre-images. 

This whole argument applies equaly in the opposite direction, from the
right. Rule tables consisting entirely of deterministic permutations, 
either left or right, are "one-way limited pre-image rules". If BOTH
left and right deterministic permutations fill the rule table (two-way
limited pre-image rules, for example n=3 rules 90, 105, 60, n=5
totalistic code 21, the "additive rules") then the pre-imaging (or in
degree) of every state turns out to be invariably equal when the basin
of attraction field is drawn; I assume this what you mean by
"zero-varience". There is proof in Martin et al.[3].
   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.
   Most rule tables have a mixture of deterministic and
(ambiguous/excluded)  permutations both left and right, which set the
rule's Z parameter. The Z parameter predicts typical basin topology, 
and the density of G of E states in state space.
 
>It is well established that for one dimensional cellular automata,  
>Gardens of Eden are absolutely computable; difficulties lie in two
>dimensions and beyond.

Can you give a reference ?

>In fact, there is no need to restrict to periodic boundary
>conditions; the procedures serve as well for quiescence at infinity or
>for boundaryless (that is, unrestrictedly infinite) automata.

Periodic boundary conditions are not required to decide if a state
is a G of E by my reverse algorithm. The occurrence of an excluded
permutation in a candidate pre-image segment disqualifies it. If all
2^(n-1) assumed starts to candidate pre-images of a given state lead to
disqualification, the state is a G of E. But given a CA with periodic
boundary conditions, a candidate pre-image may be disqualified for the
only reason that it does not comply with periodic boundary
conditions.

By the way, in more recent work I have developed a GENERAL reverse
algorithm that computes the pre-images (if any), and basins of
attraction, of Stuart Kauffman's "random Boolean networks", which may
have any arbitrary wiring and/or rule scheme for each cell. I argue
that the basins of attraction (which may be "sculpted" by a learning
algorithm) represent the networks dynamic memory[4,5]. 
   The wiring may be set to conform to 1,2 or 3-D finite CA
architecture, allowing the pre-images as well as G of E states of
higher dimensional CA to be computed without exhaustive testing.

Andy Wuensche                 contact address:
  Santa Fe Institute and          48 Esmond Road, London W4 1JQ
  University of Sussex            tel 081 995 8893, fax 081 742 2178
  wuensch@santafe.edu             email 100020.2727@compuserve.com


[1] "THE GLOBAL DYNAMICS OF CELLULAR AUTOMATA, An Atlas of Basin of
Attraction Fields of One-Dimensional Cellular Automata"
Andrew Wuensche and Mike Lesser, (Diskette included)
foreword by Christopher Langton.
Santa Fe Institute Studies in the Sciences of Complexity, Reference Vol
1, Addison-Wesley, Reading MA, phone:(800) 447 2226, IBSN 0-201-55740-1
1992  Hardcover, 250 pages, $53.75

[2] Jen,E., "Global properties of Cellular Automata", J. of Stat. 
Phys. Vol.43. Nos 1/2. April 1986.

[3]. Martin.O., A.M.Odlysko, and S.Wolfram. "Algebraic Prorerties of
Cellular Automata". Comm.Maths.Phys.93(1984),219-258.

[4] Wuensche,A., "The Ghost in the Machine; Basin of Attraction Fields
of Disordered Cellular Automata Networks", Santa Fe Institute Working
Paper 92-04-017, 1992. Submited to the proceedings of Alife III.

[5]. Wuensche,A., "Basins of Attraction in Disordered Networks", In: 
Artificial Neural Networks 2, Ed. I.Alexander and J.Taylor, Elsevier, 
Amsterdam, 1325-1344, 1992.



Newsgroups: comp.theory.cell-automata