home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / theory / cellaut / 540 < prev    next >
Encoding:
Text File  |  1992-11-19  |  6.7 KB  |  145 lines
  1. Newsgroups: comp.theory.cell-automata
  2. Path: sparky!uunet!snorkelwacker.mit.edu!bloom-beacon!INTERNET!dont-send-mail-to-path-lines
  3. From: 100020.2727@CompuServe.COM (Andrew Wuensche)
  4. Subject: basins of attraction
  5. Message-ID: <921119191627_100020.2727_EHF46-1@CompuServe.COM>
  6. Sender: root@athena.mit.edu (Wizard A. Root)
  7. Organization: The Internet
  8. Distribution: inet
  9. Date: Thu, 19 Nov 1992 19:16:28 GMT
  10. Lines: 133
  11.  
  12. re. message from Harold V. McIntosh; 
  13.  
  14. >Well, I have ordered a copy of the book; delivery has been promised
  15. >for January or February. In the meantime, it is only possible to
  16. >conjecture the contents of the book...
  17.  
  18. Sorry you have to wait so long. I hope others have found it easier to
  19. get hold of my book !? It came out in the USA in early Oct. 
  20. At the risk of an overlong message, I will try to reply to your
  21. comments, and also indicate the basis of the reverse algorithm.
  22.  
  23. > ...... and the relationship of the procedures to those
  24. >of E. F. Moore, G. A. Hedlund, M. Nasu, Erica Jen, or even myself.
  25.  
  26. > 1) Unless the counterimages are balanced, there must be a
  27. >Garden-of-Eden. Presumably this coincides with your 'limited
  28. >pre-image rules' remark above, and immediately foredooms most automata
  29. >to have Gardens of Eden.
  30.  
  31. > 2) In my early calculations of the variance in the number of
  32. >ancestors, there appeared to be a gap between the rules of
  33. >zero-variance and the others? Have you observed such an effect? Is it
  34. >real (I later decided that it probably wasn't)?
  35.  
  36. The reverse algorithm for generating pre-images described in my book
  37. [1] relates to Erica Jen's notion of deterministic structures [2]. 
  38. Entries in the rule table, say for 3-neighbour (Wolfram's elementary) 
  39. rules are grouped into pairs of neighbourhoods that differ only by
  40. their rightmost value. If a pair has different outputs, ie
  41.  
  42.               a1,a2,0 --> T     and     a1,a2,1 --> not T
  43.  
  44. then given the values of a1,a2 and T, a3 is determined. If all pairs in
  45. the rule table have "left deterministic permutations" as above then
  46. the set of pre-images of any state is easily found by assuming the
  47. start of a candidate pre-image as a1,a2......  Successive values are
  48. determined to the right. As there are 4 assumed starts, the maximum
  49. number of pre-images is 4 for any array size (in general, 2^(n-1) where
  50. n is neighbourhood size). A candidate pre-image can be disqualified if
  51. it fails a periodic boundary condition check.
  52.  
  53. A pair having the same output is an "ambiguous permutations" ie. 
  54.  
  55.        a1,a2,0 --> T     and     a1,a2,1 -->  T
  56.  
  57. and implies the "excluded permutations"
  58.  
  59.        [a1,a2,0 --> not T]   and   [a1,a2,1 --> not T] 
  60.  
  61. In this case given a1,a2 and T, a3 = 0 or 1 with equal validity
  62. (potentially increacing the number of pre-images); the occurrence of
  63. a1,a2 and not T disqualify the candidate pre-image, potentialy reducing
  64. the number of pre-images. 
  65.  
  66. This whole argument applies equaly in the opposite direction, from the
  67. right. Rule tables consisting entirely of deterministic permutations, 
  68. either left or right, are "one-way limited pre-image rules". If BOTH
  69. left and right deterministic permutations fill the rule table (two-way
  70. limited pre-image rules, for example n=3 rules 90, 105, 60, n=5
  71. totalistic code 21, the "additive rules") then the pre-imaging (or in
  72. degree) of every state turns out to be invariably equal when the basin
  73. of attraction field is drawn; I assume this what you mean by
  74. "zero-varience". There is proof in Martin et al.[3].
  75.    One-way limited pre-image rules (either left or right, not both) 
  76. must have pre-imaging less than the theoretical maximum of 2^(n-1), for
  77. example n=3 rules 30 and 45 (the proof is given in my the book). These
  78. rules result in many states having only one pre-image ("balanced"?), 
  79. and thus their basins of attraction tend to have very long transients
  80. and attractor cycles, corresponding to "chaotic" behaviour.
  81.    Most rule tables have a mixture of deterministic and
  82. (ambiguous/excluded)  permutations both left and right, which set the
  83. rule's Z parameter. The Z parameter predicts typical basin topology, 
  84. and the density of G of E states in state space.
  85.  
  86. >It is well established that for one dimensional cellular automata,  
  87. >Gardens of Eden are absolutely computable; difficulties lie in two
  88. >dimensions and beyond.
  89.  
  90. Can you give a reference ?
  91.  
  92. >In fact, there is no need to restrict to periodic boundary
  93. >conditions; the procedures serve as well for quiescence at infinity or
  94. >for boundaryless (that is, unrestrictedly infinite) automata.
  95.  
  96. Periodic boundary conditions are not required to decide if a state
  97. is a G of E by my reverse algorithm. The occurrence of an excluded
  98. permutation in a candidate pre-image segment disqualifies it. If all
  99. 2^(n-1) assumed starts to candidate pre-images of a given state lead to
  100. disqualification, the state is a G of E. But given a CA with periodic
  101. boundary conditions, a candidate pre-image may be disqualified for the
  102. only reason that it does not comply with periodic boundary
  103. conditions.
  104.  
  105. By the way, in more recent work I have developed a GENERAL reverse
  106. algorithm that computes the pre-images (if any), and basins of
  107. attraction, of Stuart Kauffman's "random Boolean networks", which may
  108. have any arbitrary wiring and/or rule scheme for each cell. I argue
  109. that the basins of attraction (which may be "sculpted" by a learning
  110. algorithm) represent the networks dynamic memory[4,5]. 
  111.    The wiring may be set to conform to 1,2 or 3-D finite CA
  112. architecture, allowing the pre-images as well as G of E states of
  113. higher dimensional CA to be computed without exhaustive testing.
  114.  
  115. Andy Wuensche                 contact address:
  116.   Santa Fe Institute and          48 Esmond Road, London W4 1JQ
  117.   University of Sussex            tel 081 995 8893, fax 081 742 2178
  118.   wuensch@santafe.edu             email 100020.2727@compuserve.com
  119.  
  120.  
  121. [1] "THE GLOBAL DYNAMICS OF CELLULAR AUTOMATA, An Atlas of Basin of
  122. Attraction Fields of One-Dimensional Cellular Automata"
  123. Andrew Wuensche and Mike Lesser, (Diskette included)
  124. foreword by Christopher Langton.
  125. Santa Fe Institute Studies in the Sciences of Complexity, Reference Vol
  126. 1, Addison-Wesley, Reading MA, phone:(800) 447 2226, IBSN 0-201-55740-1
  127. 1992  Hardcover, 250 pages, $53.75
  128.  
  129. [2] Jen,E., "Global properties of Cellular Automata", J. of Stat. 
  130. Phys. Vol.43. Nos 1/2. April 1986.
  131.  
  132. [3]. Martin.O., A.M.Odlysko, and S.Wolfram. "Algebraic Prorerties of
  133. Cellular Automata". Comm.Maths.Phys.93(1984),219-258.
  134.  
  135. [4] Wuensche,A., "The Ghost in the Machine; Basin of Attraction Fields
  136. of Disordered Cellular Automata Networks", Santa Fe Institute Working
  137. Paper 92-04-017, 1992. Submited to the proceedings of Alife III.
  138.  
  139. [5]. Wuensche,A., "Basins of Attraction in Disordered Networks", In: 
  140. Artificial Neural Networks 2, Ed. I.Alexander and J.Taylor, Elsevier, 
  141. Amsterdam, 1325-1344, 1992.
  142.  
  143.  
  144.  
  145.