Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!usc!snorkelwacker.mit.edu!bloom-beacon!dont-send-mail-to-path-lines From: ACW@YUKON.SCRC.Symbolics.COM (Allan C. Wechsler) Newsgroups: comp.theory.cell-automata Subject: Re: on Life (and Death) Message-ID: <19910322001456.2.ACW@PALLANDO.SCRC.Symbolics.COM> Date: 22 Mar 91 00:14:00 GMT References: <91Mar21.021302est.6153@neat.cs.toronto.edu> Sender: daemon@athena.mit.edu (Mr Background) Distribution: inet Organization: The Internet Lines: 47 I got two interesting responses. Date: Thu, 21 Mar 1991 02:13 EST From: Calvin Bruce Ostrum It is trivial to prove that some parent exists within what you call the "second" neighbourhood of the pattern, if any parent exists. I don't know how to prove this, and I would be interested in seeing your trivial proof. The question is, tho, is this a plausible parent? Don't know what you mean by "plausible". This problem is very interesting: I hope someone has more useful remarks to make than pointing out false statements. I agree that the problem is interesting. But given that I didn't know that the second neighborhood theorem was trivial, you can see why I asked my question. I wasn't trying to be a wet blanket -- honest. So what if Gardens of Eden exist? It doesnt affect the interestingness of the problem. Nor does the fact that much of the parent may die. Indeed, given the second neighborhood theorem. It seems very hard to compute the smallest parent, or even any parent. Angelo Wentzler's comments plus the second neighborhood theorem imply an upper bound of 2^(O(n)). Date: Thu, 21 Mar 1991 14:03 EST From: Dan Hoey In article <19910320160714.2.ACW@PALLANDO.SCRC.Symbolics.COM> you write: >In particular you contend that the parent must be contained in the >second neighborhood of the child. Can you prove this? Of course not. There could be parts of the parent arbitrarily far away that die off completely. You misunderstood because I wrote sloppily. As Calvin Ostrum observed, what I meant to say was "...that if any parent exists, some parent must be contained..." If the second neighborhood theorem were false, then we could not establish a 2^(O(N)) algorithm for finding a parent if any exists. All this implies that you could prove a pattern to be a Garden of Eden by looking (exhaustively) in some finite area for a parent, and failing to find one.