home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / theory / cellaut / 511 < prev    next >
Encoding:
Text File  |  1992-11-10  |  2.9 KB  |  57 lines
  1. Newsgroups: comp.theory.cell-automata
  2. Path: sparky!uunet!cis.ohio-state.edu!zaphod.mps.ohio-state.edu!usc!sol.ctr.columbia.edu!emory!gatech!bloom-beacon!INTERNET!dont-send-mail-to-path-lines
  3. From: MCINTOSH@UNAMVM1.BITNET ("Harold V. McIntosh")
  4. Subject: subshifts of finite type.
  5. Message-ID: <9211110719.AA13554@Early-Bird.Think.COM>
  6. X-Unparsable-Date: Tue, 10 Nov 92 23: 28:46 MEX
  7. Sender: root@athena.mit.edu (Wizard A. Root)
  8. Organization: The Internet
  9. Distribution: inet
  10. Date: Wed, 11 Nov 1992 07:20:51 GMT
  11. Lines: 44
  12.  
  13. In his recent contribution to the lore of the Garden of Eden, Lyman Hurd
  14. (<hurd(at)MATH.GATECH.EDU>) comments:
  15. -
  16. > The distinction between 1 and 2D is again vast.  In 1-d one way to specify
  17. > a set of configurations is to exclude a finite set of substrings.  The
  18. > resultant sequences form what is known as a subshift of finite type and has
  19. > a regular language description as all bi-infinite walks through a specific
  20. > labeled directed graph.  In 2D the undecidability of the tiling problem
  21. > says that given a finite set of excluded blocks, one cannot decide whether
  22. > the set described is non-empty.
  23. -
  24. One of the things which has puzzled me has been to know why the emphasis has
  25. been placed on 'subshifts of finite type' rather than on what is now called
  26. a 'sofic system.' Roy Adler and Leopold Flatto, in an expository article in
  27. the Bulletin of the American Mathematical Society, October 1991, pp 239-334,
  28. give the idea that the difference is due to the nature of the graph in which
  29. the bi-infinite walks are taken.
  30. -
  31. The difference is important, because sofic systems correspond to one
  32. dimensional
  33. cellular automata and subshifts of finite type apparently do not. The question
  34. is whether this is a historical matter, in which the knowledge of these systems
  35. gradually developed along a certain path, which was later seen not to have been
  36. the most convenient one? Or whether there is some fundamentally important
  37. difference which one has failed to comprehend?
  38. -
  39. The article in question contains an explanation of the relationship between
  40. topology and combinatorics for shift dynamical systems (and automata as well)
  41. in which the way that one defines open sets and requires commutativity with the
  42. shift operation leads naturally to the role of the functions by which automata
  43. evolve as the continuous functions for the topology.
  44. -
  45. It is not that one cannot comprehend the formal proofs in this area; it is the
  46. usual difficulty of understanding the motivations behind the mathematician's
  47. accustomed elegance. Often knowing WHY the mathematician did something is much
  48. more important than knowing HOW it was done.
  49. -
  50. Would any of the persons who have worked in this area care to comment on their
  51. experiences?
  52. -
  53. Harold V. McIntosh             |Depto. de Aplicaci'on de Microcomputadoras
  54. MCINTOSH@UNAMVM1.BITNET        |Instituto de Ciencias/UAP
  55. mcintosh@unamvm1.dgsca.unam.mx |Apdo. Postal 461
  56. (+52+22)43-6330                |72000 Puebla, Pue., MEXICO
  57.