home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / theory / cellaut / 509 < prev    next >
Encoding:
Text File  |  1992-11-10  |  4.6 KB  |  98 lines
  1. Newsgroups: comp.theory.cell-automata
  2. Path: sparky!uunet!snorkelwacker.mit.edu!bloom-beacon!INTERNET!dont-send-mail-to-path-lines
  3. From: hurd@math.gatech.EDU (Lyman Hurd)
  4. Subject: Undecidability of configurations/progression
  5. Message-ID: <9211110145.AA23882@math.gatech.edu>
  6. Sender: root@athena.mit.edu (Wizard A. Root)
  7. Organization: The Internet
  8. References: <1992Nov8.210220.29731@hellgate.utah.edu>
  9. Distribution: inet
  10. Date: Wed, 11 Nov 1992 01:45:00 GMT
  11. Lines: 85
  12.  
  13. There are two distinct categories of questions about CA, yielding four
  14. kinds of decisions.
  15.  
  16. 1) There is a distinction between finite (quiescent outside a bounded
  17. region, and infinite configurations.
  18.  
  19. 2) There is a distinction between 1 and 2 dimensions.  I am not aware of
  20. any problems which get harder as one passes from 2 to 3 but I would be
  21. interested to hear of any!
  22.  
  23. To the best of my knowledge here is what is known.
  24.  
  25. 1) FINITE - 1 or 2 DIMENSIONAL
  26.  
  27. In one dimension there is a procedure to decide whether a configuration has
  28. a predecessor.  If there exists one, it can be shown that there is a
  29. predecessor which is eventually periodic.  Furthermore you can decide if a
  30. finite configuration has a finite predecessor.  This result is (to my
  31. knowledge) due to Golze.  Proofs are not difficult.
  32.  
  33. In 2 dimensions you cannot even determine if the all-quiescent (as finite
  34. as they come) configuration has a predecessor.  This follows immediately
  35. from Berger's theorem which states that there is no general way to decide
  36. if a given set of Wang tiles (square tiles with a preferred orientation and
  37. four colored edges---tilings must have touching edges have the same colors)
  38. admits a plane tiling.  This type of construction appears many places,
  39. including Golze, Kari, Culik, Yu, and me.
  40.  
  41. 2. Decaying into a cycle.  From a finite configuration (in 1-d) it was
  42. shown by Culik and Yu.  The infinite case and in particular if all infinite
  43. configurations decay into the quiescent state was solved by Kari.
  44.  
  45. A consequence of this result are what Kari and I call aperiodic CA which
  46. have the property that all spatially periodic configurations evolve to a
  47. quiescent state, although NOT in uniform time, but not all configurations
  48. do so.  Also the only temporally periodic state is quiescent.  Such rules
  49. can be made to have highly non-trivial dynamics completely supported off
  50. the periodic points.
  51.  
  52. 3. Injectivity and surjectivity.  In one dimension there are standard
  53. constructions for showing if a CA is onto its image (i.e., has NO gardens
  54. of Eden).  If it is injective (F(x)=F(y) implies x=y) then it must be
  55. reversible (bijective---this is not obvious), and once again in 1-d a
  56. finite procedure starting with a rule table will answer this question.
  57.  
  58. In 2D Kari in his thesis showed that both questions are undecidable---i.e.,
  59. in 2D we cannot even tell if ANY GOE's exist!
  60.  
  61. One interesting corollary is the following.  Given two rules (in 1 or 2
  62. dimensions) one can decide whether they are inverses.  In one dimensions if
  63. you know the number of states per site and the radius of the rule (speed of
  64. light) one can get an effective bound on the radius of the inverse and find
  65. it by exhaustion (I am not suggesting this practically).  This bound has
  66. cryptographic implications.  In 2D Kari shows such a recursive bound cannot
  67. exist.  There must be 2D rules whose description in one dimension are
  68. arbitrarily simpler than their description in the other.
  69.  
  70. My own prejudice lies in describing sets of configurations of dynamical
  71. interest (closed and shift-invariant).  It turns out that any such set is
  72. determined by knowing all finite configurations lying within in.  In 1-d
  73. this forms a language.
  74.  
  75. The distinction between 1 and 2D is again vast.  In 1-d one way to specify
  76. a set of configurations is to exclude a finite set of substrings.  The
  77. resultant sequences form what is known as a subshift of finite type and has
  78. a regular language description as all bi-infinite walks through a specific
  79. labeled directed graph.  In 2D the undecidability of the tiling problem
  80. says that given a finite set of excluded blocks, one cannot decide whether
  81. the set described is non-empty.
  82.  
  83. In short I want to reiterate:
  84.  
  85. 1) The questions depend highly on whether one restricts to finite
  86. configurations.
  87.  
  88. 2) There is a dramatic difference between 1 and 2 dimensions.  Ironically
  89. the proofs of undecidability are usually much easier in two dimensions.
  90.  
  91. My own advice for the future is the exploration of reversible 1-D CA rules.
  92. Almost all of the results I know of are in the irreversible case.  For
  93. example I do not know the answer to the question:
  94.  
  95. Given a reversible rule F, is it decidable whether there exists N such that
  96. F^N(x)=x for all (infinite) configurations x.
  97.  
  98.