home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / theory / cellaut / 496 < prev    next >
Encoding:
Internet Message Format  |  1992-11-08  |  2.6 KB
  1. Path: sparky!uunet!zaphod.mps.ohio-state.edu!cis.ohio-state.edu!ucbvax!bloom-beacon!INTERNET!dont-send-mail-to-path-lines
  2. From: hurd@math.gatech.EDU (Lyman Hurd)
  3. Newsgroups: comp.theory.cell-automata
  4. Subject: What is Garden of Eden?
  5. Message-ID: <9211072208.AA09554@math.gatech.edu>
  6. Date: 7 Nov 92 22:08:35 GMT
  7. References: <1992Nov2.155048.2826@hellgate.utah.edu>
  8. Sender: root@athena.mit.edu (Wizard A. Root)
  9. Distribution: inet
  10. Organization: The Internet
  11. Lines: 48
  12.  
  13.  
  14.    Date: 2 Nov 92 15:50:48 MST
  15.    From: tolman%asylum.cs.utah.edu@cs.utah.edu (Kenneth Tolman)
  16.    Organization: University of Utah, CompSci Dept
  17.    Newsgroups: comp.theory.cell-automata
  18.    Sender: ca-request@Think.COM
  19.  
  20.    What is the Garden of Eden?  What was Moore's theorem about these 
  21.    configurations?
  22.  
  23.    I have been assuming that a Garden of Eden configuration is some state which
  24.    can only exist during the first time interval of a CA.... such as a 
  25.    grid of entirely on cells for the game of life.  Is this a correct
  26.    intepretation?  Are there important implications for these configurations?
  27.  
  28.  
  29. This is correct.  Specifically if the state space of the CA is X and the
  30. rule represented by a global function F: X --> X, then a configuration c in
  31. X is a GOE if and only if c in X - F(X).
  32.  
  33. From my own persppective, what are interesting are the complements of the
  34. GOE's.  or a physical system, it seems reasonable to assume that it is in
  35. steady state and therefore one assumes that even if the dynamics are
  36. irreversible one can assume that an observed state has a semi-infinite
  37. sequence of predecessors (by no means unique).
  38.  
  39. In one dimension, the GOE's for a given iteration (those configurations
  40. which can occur at time step N but not at time step N+1) collectively form
  41. a recursively enumerable set (in a sense made precise in the paper cited
  42. below but which can be explained if asked).
  43.  
  44. In [1]  showed that the set need not be recursive.  Hence it was undecidable
  45. whether a given configuration was GOE for ALL n although it IS decidable in
  46. 1-D for a specific N.  The question in 2-d is actually somewhat easier
  47. because less is true.  The undecidability of the Tiling problem (Berger's
  48. Theorem) has wide-ranging implications for 2D CA.
  49.  
  50. I thought I would throw this in since I assume that my perspective is
  51. fairly peculiar in this regard.  The notation comes from Moore's Garden of
  52. Eden Theorem for which I hope someone will jump in with a reference.  Also
  53. there are some papers of Golze which generalize the problem in several
  54. ways.  Once again I will try to dig up references but other people shoould
  55. feel free to jump in.
  56.  
  57. Hope this helps,
  58.  
  59. Lyman Hurd
  60. Iterated Systems, Inc.
  61.