home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / theory / cellaut / 512 < prev    next >
Encoding:
Text File  |  1992-11-11  |  3.1 KB  |  70 lines
  1. Newsgroups: comp.theory.cell-automata
  2. Path: sparky!uunet!secapl!Cookie!frank
  3. From: frank@Cookie.secapl.com (Frank Adams)
  4. Subject: Re: Undecidability of configurations/progression
  5. Message-ID: <1992Nov11.173807.100765@Cookie.secapl.com>
  6. Date: Wed, 11 Nov 1992 17:38:07 GMT
  7. References: <1992Nov8.210220.29731@hellgate.utah.edu> <POLLACK.92Nov9133140@dendrite.cis.ohio-state.edu>
  8. Organization: Security APL, Inc.
  9. Lines: 59
  10.  
  11. In article <POLLACK.92Nov9133140@dendrite.cis.ohio-state.edu> pollack@cis.ohio-state.edu writes:
  12. >>2) Whether a configuration is garden of eden (as demonstrated by previous
  13. >>  poster)
  14. >
  15. >there are 3 different problems:
  16. >
  17. >1)  Given a SPECIFIC finite configuration, we can run a deterministic
  18. >limited-neighborhood CA BACKWARDS one step.  Generally, one would get
  19. >lots of previous states, but a GoE would have 0 previous states.
  20. >The size of the previous states would expand at the speed of light.
  21.  
  22. This depends on exactly how you define a GoE pattern.  If I have a pattern
  23. which fits in an n by m rectangle, there are two questions I can ask:
  24.  
  25. (1) is there any previous pattern whose next step, restricted to that
  26. rectangle, is the specified pattern?
  27.  
  28. (2) is there any previous pattern whose next step is the specified pattern,
  29. with everything outside the rectangle being blank?
  30.  
  31. Question (1) can be answered as described; however I believe question (2) is
  32. the standard definition of a GoE.  And question (2) is, in fact,
  33. undecidable.
  34.  
  35. (*Very* brief outline of proof: one can make a CA for a given Turing machine
  36. such that a cell disappears iff it is (locally) part of a computation of the
  37. TM (with successive times in adjacent rows).  A row will be GoE iff the
  38. computation starting with it does not halt.  Hence the GoE problem is
  39. reducible to the halting problem.  (Note that if you allow infinite
  40. patterns, you can simply refuse to erase the halting state, inverting the
  41. result: a pattern is GoE iff the computation starting with it *does* halt.))
  42.  
  43. >2) Finding a GoE which gives rise to a PARTICULAR configuration is a
  44. >much harder problem, as it would require searching through the space
  45. >generated by operator 1. Unless the question were asked: "is this
  46. >configuration less than K generations from a GoE", it is undecideable.
  47.  
  48. It is undecideable anyhow.
  49.  
  50. >3) finally, whether or not any GoE's EXIST for a particular CA rule
  51. >might be even harder. 
  52.  
  53. However, if I remember the Scientific American article where I first
  54. encountered GoE patterns, this problem is easy: a CA has a GoE pattern iff
  55. it is not invertible.  An invertible CA A is one where there is an inverse
  56. CA B such that if A takes pattern X to pattern Y, B takes Y to X, and vice
  57. versa.
  58.  
  59. >A more interesting question might involve whether the current state in
  60. >the smallest bounding box, could have arisen from a "smaller" state.
  61. >
  62. >Then one could invert CA's to build data compression systems:
  63. >
  64. >   Start with 1011 and run rule 247 for 16325 generations,
  65. >   then run rule 343 for 932 generations, and ta da: the Mona Lisa!
  66.  
  67. You can't compress the data to less than it's information-theoretic content.
  68. A "data-compression" scheme which doesn't attack the redundencies in the
  69. original message is not likely to accomplish anything.
  70.