home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / theory / cellaut / 502 < prev    next >
Encoding:
Text File  |  1992-11-09  |  1.5 KB  |  43 lines
  1. Newsgroups: comp.theory.cell-automata
  2. Path: sparky!uunet!destroyer!gumby!ursa!uther!baljeual
  3. From: baljeual@uther.calvin.edu (Alan Baljeu)
  4. Subject: Re: Undecidability of configurations/progression
  5. Message-ID: <baljeual.721331676@uther>
  6. Sender: news@calvin.edu
  7. Organization: Calvin College
  8. References: <1992Nov8.210220.29731@hellgate.utah.edu> <BxG9GE.4n4@dcs.glasgow.ac.uk>
  9. Date: Mon, 9 Nov 1992 17:54:36 GMT
  10. Lines: 31
  11.  
  12. fraserc@dcs.glasgow.ac.uk (Campbell Fraser) writes:
  13.  
  14. >In article <1992Nov8.210220.29731@hellgate.utah.edu>, tolman%asylum.cs.utah.edu@cs.utah.edu (Kenneth Tolman) writes:
  15.  
  16. >>   There are some things which must be undecidable for cellular automata...
  17. >> see if you agree!
  18. >>
  19. >... 
  20. >> 
  21. >> 2) Whether a configuration is garden of eden (as demonstrated by previous
  22. >>   poster)
  23. >> 
  24. >...
  25.  
  26. >Surely this is. If the 'world' has length x and height y then there are 2^(x.y)
  27. >possible states. Try every one and if none lead to the alleged garden of eden 
  28. >then it is a garden of eden. If one does then make it the starting state and
  29. >then the alleged garden is reached proving that it isn't.
  30.  
  31. >Of course the problem is probably intractable.
  32.  
  33. >Excuse me if this is wrong and naive but I only just peeked at this newsgroup
  34. >and don't know a lot about CA.
  35.  
  36. For any given configuration, you can probably determine this.  The problem is 
  37. to find a general algorithm that say yes for this config, and no for that 
  38. config, that works for any config whatsoever.
  39.  
  40. CA worlds are generally unbounded, so the world has length oo and height oo.
  41.  
  42.  
  43.