home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / theory / cellaut / 493 < prev    next >
Encoding:
Internet Message Format  |  1992-11-07  |  1.7 KB
  1. Path: sparky!uunet!zaphod.mps.ohio-state.edu!cs.utexas.edu!sun-barr!ames!agate!doc.ic.ac.uk!uknet!acorn!armltd!dseal
  2. From: dseal@armltd.co.uk (David Seal)
  3. Newsgroups: comp.theory.cell-automata
  4. Subject: Re: What is Garden of Eden?
  5. Message-ID: <9408@armltd.uucp>
  6. Date: 6 Nov 92 10:37:18 GMT
  7. References: <1992Nov5.083342.23825@usage.csd.unsw.OZ.AU>
  8. Sender: dseal@armltd.uucp
  9. Distribution: comp
  10. Organization: A.R.M. Ltd, Swaffham Bulbeck, Cambs, UK
  11. Lines: 27
  12.  
  13. In article <1992Nov5.083342.23825@usage.csd.unsw.OZ.AU>
  14. brianm@plod.cbme.unzw.oz.au (Brian Murray) writes:
  15.  
  16. >What is this "Winning Ways" book to which you refer? Does it contain
  17. >much more life stuff?
  18.  
  19. "Winning Ways", by Berlekamp, Conway and Guy - sorry, don't have my copy
  20. handy, so can't give publisher details or ISBN numbers. It's in 2 volumes,
  21. and is a standard reference for mathematical games and puzzles.
  22.  
  23. Volume 2 contains a reasonably large chapter about Life, which in particular
  24. includes a sketch of how a universal computer can be assembled out of glider
  25. guns, eaters, etc. This computer can be programmed to completely
  26. self-destruct: a consequence of this is that no algorithm can exist which
  27. determines whether an arbitrary Life configuration will ultimately die out
  28. completely. (If there were such an algorithm, it could be presented with the
  29. Life universal computer, programmed to run a given program and to
  30. self-destruct when the program halts. This Life configuration would die out
  31. completely if and only if the given program halts: thus an algorithm to
  32. solve the "Life dying out" problem could be used to solve the halting
  33. problem. Since the halting problem is provably insoluble, such an algorithm
  34. cannot exist.)
  35.  
  36. David Seal
  37. dseal@armltd.co.uk
  38.  
  39. All opinions are mine only...
  40.