home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / theory / cellaut / 596 < prev    next >
Encoding:
Text File  |  1993-01-09  |  4.3 KB  |  83 lines
  1. Newsgroups: comp.theory.cell-automata
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!howland.reston.ans.net!paladin.american.edu!gatech!enterpoop.mit.edu!bloom-beacon!INTERNET!dont-send-mail-to-path-lines
  3. From: MCINTOSH@unamvm1.dgsca.unam.mx ("Harold V. McIntosh")
  4. Subject: Universal Cellular Automata.
  5. Message-ID: <9301100317.AA01184@Early-Bird.Think.COM>
  6. X-Unparsable-Date: Sat, 09 Jan 93 21: 11:59 MEX
  7. Sender: root@athena.mit.edu (Wizard A. Root)
  8. Organization: The Internet
  9. Distribution: inet
  10. Date: Sun, 10 Jan 1993 03:20:17 GMT
  11. Lines: 70
  12.  
  13. Hassan Masum <hmasum(at)ALFRED.CCS.CARLETON.CA> asks:
  14. >
  15. > What classes of 1-dimensional CAs have been shown to be capable of
  16. > supporting universal computers?  I've read about 2 or 3 specific
  17. > examples, but I'm more interested in any general results.  Also it
  18. > would be nice to know the 'simplest' 1D CA so far discovered with this
  19. > property.
  20. >
  21. That depends somewhat on how you define a universal computation. If you
  22. follow Turing's line of thought, that you have a specific algorithm or
  23. process or concept that you call computation in mind, and then set out to
  24. design a mechanism which will realize that computation, then you have one
  25. point of view.
  26. -
  27. On the other hand if you have some natural (or artificial) phenomonon which
  28. either looks or is provably complicated, you may conclude that you need an
  29. artifact at least as complicated as Turing's Universal Computer to analyze
  30. it. You might then say that your phenomonon was participating in a univerasl
  31. computation, or performing one, or whatever.
  32. -
  33. Taking the first point of view, it is not hard to conjure up a one dimensional
  34. cellular automaton which follows the lines of Turing's original design; this
  35. was already done back around the fifties, as von Neumann's ideas about cellular
  36. automata began to circulate.
  37. -
  38. There is also a famous result of Shannon, concerning the tradeoff between
  39. states and symbols in a Turing machine, whence one concludes that their product
  40. ought to be constant, whose minimal value has been a result of a certain amount
  41. of speculation. Marvin Minsky discusses the issue in his book, 'Computation:
  42. Finite and Infinite Machines.'
  43. -
  44. In recent times attention has again been paid to the issue. Karel Culick III
  45. and collaborators have discussed some tradeoffs in cellular automata, wherein
  46. the size of a neighborhood may be compensated by an increase in states. Other
  47. authors have pondered such issues as the effect of an infinite number of read
  48. heads on the automaton, or of guaranteeing an infinite supply of tape.
  49. -
  50. Specific results would not seem to go much beyond those reported by Minsky.
  51. In general, even a radius 1/2 automaton can model a Turing Machine, but the
  52. Universal Machine needs a certain minimum of states, whose exact value is not
  53. known.
  54. -
  55. If a cellular automaton cannot be modelled on a Turing Machine that is only
  56. because it operates in parallel and is infinite. So if you want to suggest
  57. that cellular automata are more powerful than Turing Machines, you are talking
  58. about models of infinity and may have an opportunity to do something original.
  59. Otherwise Turing's thesis, or Church's thesis, or whatever, is that everything
  60. that we are accustomed to call computing, can be modelled on a Turing Machine.
  61. -
  62. Stephen Wolfram, among others, has poetically referred to processes performing
  63. 'universal computations,' and we come to the second point of view mentioned
  64. above. But, in a supplement to one of A.K. Dewdney's articles in Scientific
  65. American, he states that to establish the universality of a cellular automaton
  66. it would be necessary to relate its activity to a Turing Machine, or some other
  67. model which has been shown equivalent.
  68. -
  69. One of these would be a Post Tag System, whose equivalence was established by
  70. Minsky; there is also Minsky's Register Machine, which was used by Berlecamp,
  71. Conway and Guy to prove Life universal. And of course, WireWorld would let you
  72. build a General Purpose Computer, although maybe it wouldn't have infinite
  73. memory.
  74. -
  75. Of course, you could always show that a given automaton was NOT universal
  76. by solving its halting problem. That usually takes care of very, very small
  77. automata.
  78. -
  79. Harold V. McIntosh             |Depto. de Aplicaci'on de Microcomputadoras
  80. MCINTOSH@UNAMVM1.BITNET        |Instituto de Ciencias/UAP
  81. mcintosh@unamvm1.dgsca.unam.mx |Apdo. Postal 461
  82. (+52+22)43-6330                |72000 Puebla, Pue., MEXICO
  83.