home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / theory / 2768 < prev    next >
Encoding:
Text File  |  1992-12-30  |  3.4 KB  |  73 lines
  1. Newsgroups: comp.theory
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!usc!cs.utexas.edu!qt.cs.utexas.edu!yale.edu!ira.uka.de!chx400!news.unige.ch!divsun.unige.ch!swann
  3. From: swann@divsun.unige.ch (SWANN philip)
  4. Subject: Re: Automata & Chomsky Hierarchy
  5. Message-ID: <1992Dec30.084134.833@news.unige.ch>
  6. Sender: usenet@news.unige.ch
  7. Organization: University of Geneva, Switzerland
  8. References:  <1992Dec15.162545.25338@news.unige.ch> <92357.182747RSMA410@HAIFAUVM.BITNET>
  9. Date: Wed, 30 Dec 1992 08:41:34 GMT
  10. Lines: 61
  11.  
  12. In article <92357.182747RSMA410@HAIFAUVM.BITNET>, Dan Gordon <RSMA410@HAIFAUVM.BITNET> writes:
  13. > In article <1992Dec15.162545.25338@news.unige.ch>, swann@divsun.unige.ch (SWANN
  14. > Philip) says:
  15. > >
  16. > >In Casti's book "Alternative Realities" there's a conjecture
  17. > >that Wolfram's classification of Cellular Automata into classes
  18. > >can be mapped into Chomsky's Hierarchy of Formal Languages. He
  19. > >cites Wolfram on this. Is there any recent work on the subject?
  20. > 
  21. > Cellular automata, in the unrestricted sense, have long ago been
  22. > proved to be computation universal, i.e., they can simulate any
  23. > Turing machine - see A.R. Smith III, "Simple computation-universal
  24. > cellular spaces, JACM 18(1971), 339-353.  This means, of course,
  25. > that they can also simulate any of the following: finite automata,
  26. > pushdown automata, and linear-bounded automata.  So cellular
  27. > automata can be "mapped" to the Chomsky hierarchy (if this is the
  28. > intended meaning of "mapping into the Chomsky hierarchy").
  29. > 
  30. > Wolfram, in "Statistical mechanics of cellular automata," Rev.
  31. > Modern Physics 55(1983),601-644, studies so-called _totalistic_
  32. > cellular automata.  In these automata, each state is considered
  33. > as a non-negative integer, and the state transition function
  34. > depends only on the sum of the states of a cell's neighborhood
  35. > (the sum includes the cell's own state).  Wolfram conjectured
  36. > that these automata are also computation-universal.
  37. > 
  38. > This conjecture about totalistic cellular automata was proved
  39. > true in: D. Gordon, "On the computational power of totalistic
  40. > cellular automata," Math. Systems Theory 20(1987), 43-52.
  41. > It is shown there that totalistic cellular automata can simulate
  42. > an arbitrary Turing machine in linear time - actually, twice
  43. > real time.  Needless to say, I was somewhat surprised to learn
  44. > from the above posting that this problem is still regarded by
  45. > some as a conjecture.
  46.  
  47. Sorry, my question was vague. I've now found the original
  48. reference.... The classification is of the limiting behavior of
  49. *one-dimensional* automata as:
  50.  
  51. A. The initial pattern disappears
  52. B. The initial pattern evolves to a fixed finite size
  53. C. The initial pattern grows indefinitely at a fixed rate
  54. D. The initial pattern grows and contracts with time
  55.  
  56. Casti then conjectures the following theorem:
  57.  
  58. "Class A and B cellular automata have limit sets that form
  59. regular languages. For most Class C and D automata, the
  60. regular language complexity increases monotonically with
  61. time so that the configurations obtained in the limit usually
  62. do not form a regular language. Instead, the limit sets for
  63. Class C automata appear to form context-sensitive languages,
  64. whereas those for Class D automata seem to correspond to
  65. general, unrestricted languages" (p. 71)
  66.  
  67. It's not clear from the references where Casti gets this
  68. from: he refers to books by Davis & Weyuker (1983) and
  69. Eilenberg (1974-76) and to a paper by Wolfram (1984) "Computation
  70. Theory of CA's" Comm. Math. Physics 96, pp. 15-57
  71.  
  72. Philip Swann
  73.