Xref: utzoo rec.puzzles:8220 sci.math:15511 comp.theory.cell-automata:307 Path: utzoo!news-server.csri.toronto.edu!cs.utexas.edu!uunet!mcsun!ukc!acorn!dseal From: dseal@armltd.uucp (David Seal) Newsgroups: rec.puzzles,sci.math,comp.theory.cell-automata Subject: Re: How Intelligent are the Winning Ways? Message-ID: <5539@acorn.co.uk> Date: 4 Mar 91 13:23:09 GMT References: Sender: uucp@acorn.co.uk Distribution: rec Organization: Acorn Computers Ltd, Cambridge, England Lines: 58 In article bagchi@eecs.umich.edu (Ranjan Bagchi) writes: > > How well-regarded is the stuff in 'Winning Ways' by >Berkamp, Conway, and Guy? Prior to looking at it, I was under the ^^^^^^^ Berlekamp, I believe. >impression that it was basically a book of recerational mathematics, >albeit with sound math behind it. > Anyway, I looked it up today because I'd heard of some work in >it screwing around with Conway's Life ;), and trying to show how to >build a computing machine with an appropriate configuration. > > Anyway...some of the initial proofs I have no problem with, >until the author mentions some wonderful things which a Life computer >could do, if there were some kind of closed form way to determine what >a given Life configuration would stabilize out to. This is where I >balked... seeing that a Turing Machine is definitely constructable in Life >if you can do a computing machine, then the author just described the >Halting Problem, and treats it like it's something decidable. I'm afraid you're missing the point. The overall argument is: If there were a "closed form way" to determine the fate of a given Life configuration, then we could do all sorts of "wonderful things". But it is known that there are such things that we cannot do. Therefore there cannot be such a "closed form way". The exact "wonderful thing we cannot do" to use is a matter of personal choice. The authors use the known fact that there are undecidable problems in number theory. Your argument uses the known fact that the Turing machine halting problem is undecidable. There are all sorts of other arguments, all more or less equivalent and all leading to the same conclusion. I can see advantages to both arguments. Your argument about the Turing machine is closer to what the Life computer actually is. However, I believe the argument about undecidable problems in number theory is a better one for the book: the authors can reasonably assume that anyone who has followed them to that point in the book knows what a simple mathematical formula means, but not that they know what a Turing machine is! So their particular choice of argument probably makes the book some 10-20 pages shorter than your one... Incidentally, how would one go about building a Life Turing machine? I can see one very long-winded technique, with a stationary tape and a moving state machine: the state machine could move by emitting fleets of gliders to (a) destroy itself; (b) reassemble an exact copy of itself one tape spacing to the left or right. However, this seems like an awful lot of work: a moving tape, stationary state machine Turing machine would seem a lot more efficient. Any ideas how the moving tape might be constructed? David Seal dseal@acorn.co.uk Standard disclaimers apply.