home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / theory / cellaut / 523 < prev    next >
Encoding:
Text File  |  1992-11-17  |  2.2 KB  |  44 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/progres
  5. Message-ID: <1992Nov16.202909.38816@Cookie.secapl.com>
  6. Date: Mon, 16 Nov 1992 20:29:09 GMT
  7. References: <1992Nov11.173807.100765@Cookie.secapl.com> <1e1q25INNmo3@seven-up.East.Sun.COM>
  8. Organization: Security APL, Inc.
  9. Lines: 33
  10.  
  11. In article <1e1q25INNmo3@seven-up.East.Sun.COM> hoppie@nemesis.East.Sun.COM writes:
  12. >In article 100765@Cookie.secapl.com, frank@Cookie.secapl.com (Frank Adams) writes:
  13. >>This depends on exactly how you define a GoE pattern.  If I have a pattern
  14. >>which fits in an n by m rectangle, there are two questions I can ask:
  15. >[...question (1) deleted...]
  16. >>(2) is there any previous pattern whose next step is the specified pattern,
  17. >>with everything outside the rectangle being blank?
  18.  
  19. This is perhaps subject to misinterpretation, especially with (1) deleted.
  20. (2) says there is a pattern A, which generates exactly the pattern B as the
  21. next step.  (1) Says there is a pattern A, such that the pattern it
  22. generates, B', intersected with the rectangle, gives the target pattern B.
  23. There was no intent to constrain the previous pattern A; quite the contrary.
  24.  
  25. >>Question (1) can be answered as described; however I believe question (2) is
  26. >>the standard definition of a GoE.  And question (2) is, in fact,
  27. >>undecidable.
  28. >[...Proof concerning (2) deleted...]
  29. >
  30. >Suppose I have a 3x3 rectangle, in which I have placed a diamond.  I
  31. >can tell you, with certainty, that there is a pattern with everything
  32. >outside the 3x3 rectangle blank for which the diamond is the next
  33. >step.  Thus for a specific configuration, of a certain size, question
  34. >(2) is decidable.
  35.  
  36. An "undecidable" problem is one where there is no way of finding an answer
  37. in general.  There may indeed be (and usually are) many individual cases
  38. where the answer is known, one way or the other.
  39.  
  40. For example, there are many individual programs (of arbitrary length) which
  41. we can prove will halt; and many others (also of arbitrary length) which we
  42. can prove will not halt.  But, *in general*, there is no way to know when a
  43. program will halt; some cases are hard.
  44.