home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / theory / cellaut / 501 < prev    next >
Encoding:
Internet Message Format  |  1992-11-09  |  1.3 KB
  1. Path: sparky!uunet!pipex!warwick!uknet!glasgow!fraserc
  2. From: fraserc@dcs.glasgow.ac.uk (Campbell Fraser)
  3. Newsgroups: comp.theory.cell-automata
  4. Subject: Re: Undecidability of configurations/progression
  5. Message-ID: <BxG9GE.4n4@dcs.glasgow.ac.uk>
  6. Date: 9 Nov 92 13:00:14 GMT
  7. References: <1992Nov8.210220.29731@hellgate.utah.edu>
  8. Organization: Glasgow University Computing Science Dept.
  9. Lines: 30
  10.  
  11. In article <1992Nov8.210220.29731@hellgate.utah.edu>, tolman%asylum.cs.utah.edu@cs.utah.edu (Kenneth Tolman) writes:
  12.  
  13. >   There are some things which must be undecidable for cellular automata...
  14. > see if you agree!
  15. >
  16. ... 
  17. > 
  18. > 2) Whether a configuration is garden of eden (as demonstrated by previous
  19. >   poster)
  20. > 
  21. ...
  22.  
  23. Surely this is. If the 'world' has length x and height y then there are 2^(x.y)
  24. possible states. Try every one and if none lead to the alleged garden of eden 
  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.  
  28. Of course the problem is probably intractable.
  29.  
  30. Excuse me if this is wrong and naive but I only just peeked at this newsgroup
  31. and don't know a lot about CA.
  32.  
  33. Campbell
  34.  
  35.  
  36.  
  37. -- 
  38. Hi, I'm a .signature virus. Copy me to yours and then wipe all your files.
  39. Campbell Fraser: fraserc@dcs.glasgow.ac.uk
  40. Computing Science Department, University of Glasgow, Glasgow G12 8QQ
  41.