home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / theory / cellaut / 500 < prev    next >
Encoding:
Text File  |  1992-11-08  |  1.2 KB  |  33 lines
  1. Newsgroups: comp.theory.cell-automata
  2. Path: sparky!uunet!caen!hellgate.utah.edu!asylum.cs.utah.edu!tolman
  3. From: tolman%asylum.cs.utah.edu@cs.utah.edu (Kenneth Tolman)
  4. Subject: Undecidability of configurations/progression
  5. Date: 8 Nov 92 21:02:19 MST
  6. Message-ID: <1992Nov8.210220.29731@hellgate.utah.edu>
  7. Organization: University of Utah, CompSci Dept
  8. Lines: 23
  9.  
  10.   There are some things which must be undecidable for cellular automata...
  11. see if you agree!
  12.  
  13. 1) Decaying into a cycle.  For any CA capable of supporting universal
  14.   computation, it could be set up to perform some computation.  If that
  15.   computation fell into a cycle, it would be non halting, and thus we
  16.   would have a decision procedure for halting or non halting for Turing
  17.   machines.  Thus, for at least a certain class of CA, there can be no
  18.   decision procedure determining whether they go into a cycle or not.
  19.   (perhaps for weaker CA as well?)
  20.  
  21. 2) Whether a configuration is garden of eden (as demonstrated by previous
  22.   poster)
  23.  
  24. 3) Whether given state A will evolve to given state B... as before, this
  25.   could not be decidable for we would have a decision procedure for
  26.   halting or non halting.
  27.  
  28.  
  29. What other things are not decidable for CA?
  30.  
  31.  
  32.  
  33.