home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / theory / cellaut / 503 < prev    next >
Encoding:
Text File  |  1992-11-09  |  2.4 KB  |  55 lines
  1. Newsgroups: comp.theory.cell-automata
  2. Path: sparky!uunet!ukma!darwin.sura.net!zaphod.mps.ohio-state.edu!magnus.acs.ohio-state.edu!cis.ohio-state.edu!dendrite.cis.ohio-state.edu!pollack
  3. From: pollack@dendrite.cis.ohio-state.edu (Jordan B Pollack)
  4. Subject: Re: Undecidability of configurations/progression
  5. In-Reply-To: tolman%asylum.cs.utah.edu@cs.utah.edu's message of 8 Nov 92 21: 02:19 MST
  6. Message-ID: <POLLACK.92Nov9133140@dendrite.cis.ohio-state.edu>
  7. Originator: pollack@dendrite.cis.ohio-state.edu
  8. Sender: news@cis.ohio-state.edu (NETnews        )
  9. Reply-To: pollack@cis.ohio-state.edu
  10. Organization: Ohio State Computer Science
  11. References: <1992Nov8.210220.29731@hellgate.utah.edu>
  12. Date: Mon, 9 Nov 1992 18:31:40 GMT
  13. Lines: 40
  14.  
  15. >2) Whether a configuration is garden of eden (as demonstrated by previous
  16. >  poster)
  17.  
  18. there are 3 different problems:
  19.  
  20. 1)  Given a SPECIFIC finite configuration, we can run a deterministic
  21. limited-neighborhood CA BACKWARDS one step.  Generally, one would get
  22. lots of previous states, but a GoE would have 0 previous states.
  23. The size of the previous states would expand at the speed of light.
  24.  
  25. To do this is straightforward but excessive in computer time. In a 3
  26. by 3 neighborhood, like LIFE, you just enumerate the number of
  27. 9-tuples which give rise to either state of a cell, and run an
  28. assumption-based constraint propagation algorithm to ensure a
  29. consistent labelling of each cell. Each assumption would multiply
  30. the number of solutions.
  31.  
  32. 2) Finding a GoE which gives rise to a PARTICULAR configuration is a
  33. much harder problem, as it would require searching through the space
  34. generated by operator 1. Unless the question were asked: "is this
  35. configuration less than K generations from a GoE", it is undecideable.
  36.  
  37. 3) finally, whether or not any GoE's EXIST for a particular CA rule
  38. might be even harder. 
  39.  
  40. A more interesting question might involve whether the current state in
  41. the smallest bounding box, could have arisen from a "smaller" state.
  42.  
  43. Then one could invert CA's to build data compression systems:
  44.  
  45.    Start with 1011 and run rule 247 for 16325 generations,
  46.    then run rule 343 for 932 generations, and ta da: the Mona Lisa!
  47.  
  48.  
  49.  
  50. -- 
  51. Jordan Pollack                            Assistant Professor
  52. CIS Dept/OSU                              Laboratory for AI Research
  53. 2036 Neil Ave                             Email: pollack@cis.ohio-state.edu
  54. Columbus, OH 43210                        Phone: (614)292-4890 (then * to fax)
  55.