home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / theory / cellaut / 533 < prev    next >
Encoding:
Text File  |  1992-11-18  |  3.1 KB  |  63 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: MCINTOSH@UNAMVM1.BITNET ("Harold V. McIntosh")
  4. Subject: Basins of attraction.
  5. Message-ID: <9211181017.AA17646@Early-Bird.Think.COM>
  6. X-Unparsable-Date: Tue, 17 Nov 92 00: 30:46 MEX
  7. Sender: root@athena.mit.edu (Wizard A. Root)
  8. Organization: The Internet
  9. Distribution: inet
  10. Date: Wed, 18 Nov 1992 10:18:24 GMT
  11. Lines: 50
  12.  
  13. Andrew Wuensche <100020.2727(at)COMPUSERVE.COM> (Mon, 16 Nov 1992 08:23:16
  14. EST) remarks:
  15. >
  16. > For finite CA with periodic boundary conditions there is a proceedure.
  17. > Checking if a state is a G of E follows from computing its pre-images,
  18. > if any. This can be done without exhaustive testing. The proceedure is
  19. > described for 1-D CA (and the software included) in my recently
  20. > published book, (see below). The G of E density in state space of a
  21. > given CA rule is approx predictable by the rule's Z parameter. For most
  22. > of rule-space with very few exceptions (the limited pre-image rules),
  23. > most states in state-space are G of E states.
  24. >    If anyone out there gets around to reading the book, or
  25. > experimenting with the software, I would welcome comments or
  26. > discussion.
  27. >
  28. Well, I have ordered a copy of the book; delivery has been promised for
  29. January or February. In the meantime, it is only possible to conjecture
  30. the contents of the book, and the relationship of the procedures to those
  31. of E. F. Moore, G. A. Hedlund, M. Nasu, Erica Jen, or even myself. It is
  32. well established that for one dimensional cellular automata, Gardens of
  33. Eden are absolutely computable; difficulties lie in two dimensions and
  34. beyond. In fact, there is no need to restrict to periodic boundary
  35. conditions; the procedures serve as well for quiescence at infinity or
  36. for boundaryless (that is, unrestrictedly infinite) automata.
  37. -
  38. It is necessary to commiserate with a remark made by Burton Voorhees here
  39. recently about his article on this topic having disappeared into a black
  40. hole. Two articles of my own have suffered the same fate. Is this traffic
  41. entirely one-way?
  42. -
  43. In the meantime, here are a couple of questions in the way of making a
  44. discussion. 1) Unless the counterimages are balanced, there must be a
  45. Garden-of-Eden. Presumably this coincides with your 'limited pre-image
  46. rules' remark above, and immediately foredooms most automata to have
  47. Gardens of Eden.
  48. -
  49. 2) In my early calculations of the variance in the number of ancestors,
  50. there appeared to be a gap between the rules of zero-variance and the
  51. others? Have you observed such an effect? Is it real (I later decided
  52. that it probably wasn't)?
  53. -
  54. In any event, I look forward to seeing the book. To formulate our ideas
  55. about automata well, it is convenient to have compilations of data to look
  56. at. I have probably turned to the appendices in Wolfram's book more often
  57. than I have consulted any of the other parts.
  58. -
  59. Harold V. McIntosh             |Depto. de Aplicaci'on de Microcomputadoras
  60. MCINTOSH@UNAMVM1.BITNET        |Instituto de Ciencias/UAP
  61. mcintosh@unamvm1.dgsca.unam.mx |Apdo. Postal 461
  62. (+52+22)43-6330                |72000 Puebla, Pue., MEXICO
  63.