home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / theory / cellaut / 516 < prev    next >
Encoding:
Text File  |  1992-11-12  |  1.7 KB  |  44 lines
  1. Newsgroups: comp.theory.cell-automata
  2. Path: sparky!uunet!charon.amdahl.com!pacbell.com!sgiblab!swrinde!emory!gatech!bloom-beacon!INTERNET!dont-send-mail-to-path-lines
  3. From: hurd@math.gatech.EDU (Lyman Hurd)
  4. Subject: subshifts of finite type.
  5. Message-ID: <9211120153.AA28752@math.gatech.edu>
  6. Sender: root@athena.mit.edu (Wizard A. Root)
  7. Organization: The Internet
  8. References: <9211110719.AA13554@Early-Bird.Think.COM>
  9. Distribution: inet
  10. Date: Thu, 12 Nov 1992 01:53:14 GMT
  11. Lines: 31
  12.  
  13. Funny, a friend, Mike Boyle, has been trying to convince me to generalize
  14. from cellular automata to SFT's!  Basically the general consensus if that
  15. subshifts of finite type are horizontal and cellular automata vertical.
  16.  
  17. What I mean by that is that is that a cellular automaton is a map commuting
  18. with the shift, whereas a subshift of finite type is defined as a shift
  19. map.
  20.  
  21. A sofic system by definition is the image of a subshift of finite type
  22. under a cellular automaton map.  All sofic systems arise this way, although
  23. not all arise as images of the full shift.
  24.  
  25. Some SFT's do arise in CA dynamics.  In many such cases the cellular
  26. automaton stabilizes:
  27.  
  28. F^n(X) = F^m(X) as sets for all n,m>N.
  29.  
  30. I was able to show (it is not hard) that if the limit set (the intersection
  31. of forward images) is a subshift of finite type, the rule must stabilize in
  32. this manner.  I conjectured that the converse was true---that whenever a
  33. rule stabilized it must do so as a subshift of finite type.  Boyle and I
  34. later showed this conjecture is false.  The subject of stable limit sets
  35. appears to be deep.
  36.  
  37. The motivation for studying subshifts of finite type belongs to the ergodic
  38. theorists and I have forwarded your inquiry in the hopes of getting that
  39. persepctive.
  40.  
  41.  
  42. Lyman Hurd
  43. Iterated Systems, Inc.
  44.