home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / theory / cellaut / 626 < prev    next >
Encoding:
Internet Message Format  |  1993-01-25  |  3.1 KB
  1. Path: sparky!uunet!paladin.american.edu!howland.reston.ans.net!zaphod.mps.ohio-state.edu!rpi!ghost.dsi.unimi.it!insa-lyon.fr!univ-lyon1.fr!frmop11!barilvm!technion!haifauvm!rsma410
  2. Organization: University of Haifa - Mt. Carmel Haifa, Israel.
  3. Date: Monday, 25 Jan 1993 15:45:49 IST
  4. From: Dan Gordon <RSMA410@HAIFAUVM.BITNET>
  5. Message-ID: <93025.154549RSMA410@HAIFAUVM.BITNET>
  6. Newsgroups: comp.theory.cell-automata
  7. Subject: Re: cellular automata with different rules at each site
  8. References:  <C188rz.2Jq0@austin.ibm.com>
  9. Lines: 49
  10.  
  11. In article <105853@netnews.upenn.edu>, bill@amy.med.upenn.edu (Bill Tozier)
  12. says:
  13. >  Is anyone familiar with any work that's been done with
  14. >cellular automata in which the rules for any given cell are fixed,
  15. >but may be different for different cells? I'm currently looking
  16. >(on the back of an envelope, literally) at behavior of 1D, neighborhood-3
  17. >2-state automata when each cell has a random rule table. Without
  18. >much stretching, this type of automaton would seem to be a re-description
  19. >of a class of networks that includes Boolean nets (a research
  20. >specialty in these parts).
  21.  
  22. It's not clear what you mean by "random rule table".  This can be
  23. interpreted as a probabilistic automaton.  It can also be interpreted
  24. as meaning that in every cell, the rule table is fixed (and not
  25. probabilistic), but the choice of which rule table goes in which
  26. cell is random.  A consequence of this is that more than one rule
  27. table can appear infinitely many times in the initial configuration.
  28.  
  29. Assuming you are referring to the second possiblilty, the answer is
  30. simple:  There are only 256 such rule tables (or transition functions)
  31. so your automata can be simulated by homogeneous automata with 512
  32. states, in which the initial configuration is chosen randomly and
  33. infinitely many cells may be in a non-quiescent state.
  34.  
  35. Further explanations:  a rule table (in the type of automaton that
  36. you use) is a function from the set of all triples of 0,1 to the
  37. set {0,1}, and there are 256 such functions - call them T_1...T_256.
  38. The homogeneous automata that will simulate these will have states
  39. of the type (A, i), where A is in {0,1} and 1 <= i <= 256; a total
  40. of 512 states.  The rules for the homogeneous automata are as follows:
  41.  
  42. If a cell is in state (A, i), its left neighbor in state (B, j),
  43. and its right neighbor is in state (C, k), then simply apply rule
  44. T_i to the 3-neighborhood B-A-C.  Suppose rule T_i changes state A
  45. to state D, then the simulating automaton should change the current
  46. state (A, i) to state (D, i).  Note that i does not change.
  47.  
  48. The simulation is now straightforward:  a cell in state A, having rule
  49. table T_i is simply simulated by a homogeneous automaton in state (A, i).
  50.  
  51. The usual assumption in cellular automata is that in the initial
  52. configuration, all but a finite number of cells are in a special state
  53. called the "quiescent state".  However, in your automata, you allow
  54. more than one rule table to appear infinitely many times, so the
  55. simulating automata must also be allowed to have more than one state
  56. appear infinitely many times.  I believe this has been looked at
  57. in the literature, but I have no references available.
  58.  
  59. Dan Gordon.
  60.