home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / theory / 2759 < prev    next >
Encoding:
Internet Message Format  |  1992-12-26  |  2.1 KB
  1. Path: sparky!uunet!usc!rpi!ghost.dsi.unimi.it!univ-lyon1.fr!frmop11!barilvm!technion!haifauvm!rsma410
  2. Organization: University of Haifa.
  3. Date: Tuesday, 22 Dec 1992 18:27:47 IST
  4. From: Dan Gordon <RSMA410@HAIFAUVM.BITNET>
  5. Message-ID: <92357.182747RSMA410@HAIFAUVM.BITNET>
  6. Newsgroups: comp.theory
  7. Subject: Re: Automata & Chomsky Hierarchy
  8. References:  <1992Dec15.162545.25338@news.unige.ch>
  9. Lines: 33
  10.  
  11. In article <1992Dec15.162545.25338@news.unige.ch>, swann@divsun.unige.ch (SWANN
  12. Philip) says:
  13. >
  14. >In Casti's book "Alternative Realities" there's a conjecture
  15. >that Wolfram's classification of Cellular Automata into classes
  16. >can be mapped into Chomsky's Hierarchy of Formal Languages. He
  17. >cites Wolfram on this. Is there any recent work on the subject?
  18.  
  19. Cellular automata, in the unrestricted sense, have long ago been
  20. proved to be computation universal, i.e., they can simulate any
  21. Turing machine - see A.R. Smith III, "Simple computation-universal
  22. cellular spaces, JACM 18(1971), 339-353.  This means, of course,
  23. that they can also simulate any of the following: finite automata,
  24. pushdown automata, and linear-bounded automata.  So cellular
  25. automata can be "mapped" to the Chomsky hierarchy (if this is the
  26. intended meaning of "mapping into the Chomsky hierarchy").
  27.  
  28. Wolfram, in "Statistical mechanics of cellular automata," Rev.
  29. Modern Physics 55(1983),601-644, studies so-called _totalistic_
  30. cellular automata.  In these automata, each state is considered
  31. as a non-negative integer, and the state transition function
  32. depends only on the sum of the states of a cell's neighborhood
  33. (the sum includes the cell's own state).  Wolfram conjectured
  34. that these automata are also computation-universal.
  35.  
  36. This conjecture about totalistic cellular automata was proved
  37. true in: D. Gordon, "On the computational power of totalistic
  38. cellular automata," Math. Systems Theory 20(1987), 43-52.
  39. It is shown there that totalistic cellular automata can simulate
  40. an arbitrary Turing machine in linear time - actually, twice
  41. real time.  Needless to say, I was somewhat surprised to learn
  42. from the above posting that this problem is still regarded by
  43. some as a conjecture.
  44.