home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / theory / cellaut / 545 < prev    next >
Encoding:
Internet Message Format  |  1992-11-21  |  2.0 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: Undecidability of configurations/progression
  5. Message-ID: <9211211708.AA14989@math.gatech.edu>
  6. Date: 21 Nov 92 17:08:51 GMT
  7. References: <1992Nov11.173807.100765@Cookie.secapl.com>
  8. Sender: root@athena.mit.edu (Wizard A. Root)
  9. Distribution: inet
  10. Organization: The Internet
  11. Lines: 38
  12.  
  13. >However, if I remember the Scientific American article where I first
  14. >encountered GoE patterns, this problem is easy: a CA has a GoE pattern iff
  15. >it is not invertible.  An invertible CA A is one where there is an inverse
  16. >CA B such that if A takes pattern X to pattern Y, B takes Y to X, and vice
  17. >versa.
  18.  
  19. Whoaaa.  This is certainly NOT true.  There are two different properties of
  20. a CA:
  21.  
  22. 1) The CA is surjective, i.e., for all configurations y there exists (at
  23. least one) configuration x such that F(x)=y.  A CA is surjective (or
  24. ``onto'') if and only if it has no GOE's.
  25.  
  26. 2) The CA is injective, i.e., for all configurations x not = y, F(x) not =
  27. F(y). 
  28.  
  29. For a general set map there exists a third condition:
  30.  
  31. 3) A map is bijective if 1) and 2) hold.  In this case there exists an
  32. inverse map.
  33.  
  34. For CA, however, 2 implies 3.  Also if a CA has a set-theoretic inverse,
  35. that inverse is also a CA.  Reference Hedlund.
  36.  
  37. It is NOT the case that 1 implies 2.  Take the 1-d rule Wolfram's
  38. elementary rule 90 with 2 states per site and each site in the next
  39. generation takes the values of the mod 2 sum of its neighbors (but not its
  40. predecessor).
  41.  
  42. In one dimension lots of proofs have been given of the fact that
  43. injectivity (=bijectivity) and surjectivity are decidable.
  44.  
  45. In his thesis, however, Kari showed that BOTH questions are undecidable for
  46. a general 2-D CA.  The proof is highly non-trivial and required
  47. strengthening Berger's Theorem on the undecidability of plane tilings
  48.  
  49. Lyman Hurd
  50. Iterated Systems, Inc.
  51.