home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / theory / cellaut / 505 < prev    next >
Encoding:
Internet Message Format  |  1992-11-09  |  2.4 KB
  1. Path: sparky!uunet!usc!hela.iti.org!cs.widener.edu!iggy.GW.Vitalink.COM!pacbell.com!decwrl!decwrl!atha!aupair.cs.athabascau.ca!burt
  2. From: burt@aupair.cs.athabascau.ca (Burt Voorhees)
  3. Newsgroups: comp.theory.cell-automata
  4. Subject: Re: Undecidability of configurations/progression
  5. Message-ID: <burt.721344629@aupair.cs.athabascau.ca>
  6. Date: 9 Nov 92 21:30:29 GMT
  7. References: <1992Nov8.210220.29731@hellgate.utah.edu> <BxG9GE.4n4@dcs.glasgow.a
  8. Sender: news@cs.athabascau.ca
  9. Lines: 44
  10.  
  11. >fraserc@dcs.glasgow.ac.uk (Campbell Fraser) writes:
  12.  
  13. >>In article <1992Nov8.210220.29731@hellgate.utah.edu>, tolman%asylum.cs.utah.e
  14. du@cs.utah.edu (Kenneth Tolman) writes:
  15. >>>   There are some things which must be undecidable for cellular automata...
  16. >>> see if you agree!
  17.  
  18. >>> 2) Whether a configuration is garden of eden (as demonstrated by previous
  19. >>>   poster)
  20.  
  21. >>Surely this is. If the 'world' has length x and height y then there are 2^(x.
  22. y)
  23. >>possible states. Try every one and if none lead to the alleged garden of eden
  24.  
  25. >>then it is a garden of eden. If one does then make it the starting state and
  26. >>then the alleged garden is reached proving that it isn't.
  27. >>Of course the problem is probably intractable.
  28.  
  29.  
  30. >For any given configuration, you can probably determine this.  The problem is
  31. >to find a general algorithm that say yes for this config, and no for that
  32. >config, that works for any config whatsoever.
  33.  
  34. >CA worlds are generally unbounded, so the world has length oo and height oo.
  35.  
  36. For any finite configuration, however, there is a proceedure which will
  37. say whether or not it is GofE.  A very computationally intensive proceedure...
  38. If I take a state space of half-infinite 0,1 strings then one of these
  39. will be Gof E if it contains any finite string which has no pre-image,
  40. that seems to say that it will not be GofE if it contains no such finite
  41. substrings, although I am no longer entirely certain about that.
  42. For looking at finite strings and determining whether or not they have
  43. pre-images, however, there is a graph theoretic based proceedure.  I've
  44. had a paper sitting at Physica D for over a year now which describes this
  45. (they must be having some kind of editorial problems there, they used
  46. to give reports rather quickly...).  Anybody who is interested send me
  47. a snail mail address and I'll forward a pre-print.
  48. Burton Voorhees
  49. Faculty of Science
  50. Athabasca University
  51. Box 10,000
  52. Athabasca, AB
  53. CANADA   T0G 2R0
  54. burt@aupair.cs.athabascau.ca
  55.