home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / theory / cellaut / 518 < prev    next >
Encoding:
Internet Message Format  |  1992-11-14  |  1.9 KB
  1. Path: sparky!uunet!charon.amdahl.com!pacbell.com!ames!sun-barr!news2me.EBay.Sun.COM!seven-up.East.Sun.COM!nemesis!hoppie
  2. From: hoppie@nemesis.East.Sun.COM (Tom Hopkins)
  3. Newsgroups: comp.theory.cell-automata
  4. Subject: Re: Undecidability of configurations/progres
  5. Date: 14 Nov 1992 02:59:17 GMT
  6. Organization: Sun Microsystems, Inc., Billerica, MA. 
  7. Lines: 30
  8. Distribution: world
  9. Message-ID: <1e1q25INNmo3@seven-up.East.Sun.COM>
  10. References: <1992Nov11.173807.100765@Cookie.secapl.com>
  11. Reply-To: hoppie@nemesis.East.Sun.COM
  12. NNTP-Posting-Host: nemesis.east.sun.com
  13.  
  14. (A note to the readers:  I am about to dive off into an area I have
  15. little or no knowledge or experience about, and if what I say sounds
  16. like the ravings of an idiot, there is good reason for it.)
  17.  
  18. In article 100765@Cookie.secapl.com, frank@Cookie.secapl.com (Frank Adams) writes:
  19. >This depends on exactly how you define a GoE pattern.  If I have a pattern
  20. >which fits in an n by m rectangle, there are two questions I can ask:
  21. [...question (1) deleted...]
  22. >(2) is there any previous pattern whose next step is the specified pattern,
  23. >with everything outside the rectangle being blank?
  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. Have I missed the point of this line of discussion entirely, or is
  37. there some size limit below which the halting problem is solvable?
  38.  
  39. Tom Hopkins <hoppie@turbo.east.sun.com>
  40. (I reiterate:  I could be saying something wholly idiotic.  If this is
  41. so, please explain to me that this is so.)
  42.  
  43.  
  44.