angelo@gem.stack.urc.tue.nl (Angelo Wentzler) (03/19/91)
Life is and has always been very intriguing to me. I have followed the recent CA-in-life discussion with much interest, although I think some of the articles are a bit vague. Not everyone knows about all the patterns discussed, you know! Of course I wanted to check all these theories and constructions, and I went in search of a life program. I have several versions now. One of those programs was accompanied by an interesting utility called lifesearch. It could be used to find cyclic patterns with a period of any number of generations. It can also be used to find parents of generations, although with one slight problem: it always tries to find 'cyclic' parents. What I would like to know is, if there are any programs available that find *all* parents of a given pattern, or better still, find a parent with minimal size (both in number of cells and in size of 'surrounding box'). I don't expect such a minimal parent to be unique, even if neglecting rotations etc. I have tried to make such a program myself (death), but all I could manage was a routine that simply tried all possibilities. This could be improved by restricting the number of cells the parent could have etc. for example, if a pattern has N cells, its parent can maximally have 3*N cells, and must minimally have 1/3*N cells. Furthermore, only those cells directly neighbouring the cells of the child, and the cells directly neighbouring those neighbours could have been part of the parent. So this restricts the size of the pattern both in number of cells and in 'surface covered'. Are there any more improvements possible? I don't think you can make life-ish rules for 'death'. Is there a more intelligent approach than mine anyway? Angelo Wentzler -- -- angelo@stack.urc.tue.nl (internet) "Don't knock masturbation. It's sex with someone you love." -Woody Allen
ACW@YUKON.SCRC.Symbolics.COM (Allan C. Wechsler) (03/21/91)
Date: Mon, 18 Mar 1991 12:51 EST
From: angelo@gem.stack.urc.tue.nl (Angelo Wentzler)
Life is and has always been very intriguing to me. I have followed the recent
CA-in-life discussion with much interest, although I think some of the articles
are a bit vague. Not everyone knows about all the patterns discussed, you know!
Of course I wanted to check all these theories and constructions, and I went
in search of a life program. I have several versions now.
One of those programs was accompanied by an interesting utility called
lifesearch. It could be used to find cyclic patterns with a period of any number
of generations. It can also be used to find parents of generations, although
with one slight problem: it always tries to find 'cyclic' parents. What I would
like to know is, if there are any programs available that find *all* parents
of a given pattern, or better still, find a parent with minimal size (both in
number of cells and in size of 'surrounding box'). I don't expect such a
minimal parent to be unique, even if neglecting rotations etc.
The "Garden of Eden" theorem proves that this is sometimes impossible.
There are patterns that have no parents at all.
I have tried to make such a program myself (death), but all I could manage was
a routine that simply tried all possibilities. This could be improved by
restricting the number of cells the parent could have etc.
for example, if a pattern has N cells, its parent can maximally have 3*N cells,
and must minimally have 1/3*N cells. Furthermore, only those cells directly
neighbouring the cells of the child, and the cells directly neighbouring those
neighbours could have been part of the parent. So this restricts the size of
the pattern both in number of cells and in 'surface covered'.
Except for your comment about the minimum size of a pattern, most of
this is false. Large parts of the parent could die off. The parent
could be much larger than the child.
In particular you contend that the parent must be contained in the
second neighborhood of the child. Can you prove this? It might be
true, but offhand it seems difficult to establish.
Allan C. WechslerACW@YUKON.SCRC.Symbolics.COM (Allan C. Wechsler) (03/22/91)
I got two interesting responses.
Date: Thu, 21 Mar 1991 02:13 EST
From: Calvin Bruce Ostrum <cbo@cs.toronto.edu>
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 <hoey@etl.army.mil>
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.ACW@YUKON.SCRC.Symbolics.COM (Allan C. Wechsler) (03/29/91)
Date: Wed, 27 Mar 1991 12:51 EST
From: Paul Crowley <aipdc@castle.edinburgh.ac.uk>
What's the simplest known pattern that has no parent?
Winning Ways p. 829 gives:
xxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxx
x x x x x x xxxx xx xxx xxx xx xx
xxxxxxxxxxxxx x x xxx xxx xxx xx
x x x x x x xx xxxxx xxx xxx xxxx
x x x x x x xxx x xxx xxx xx x x
xxxxxxxxxxxxxx xxxx xxx xxx xxxxx
x x x x x x xxx xxxx xxx xxx x x
x x x x x x x x x xx xxx xxx x xx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
I understand Schroeppel was in the group that discovered this; I don't
know his net address but I've CC'd Gosper and perhaps he'd be willing to
forward to Schroeppel our request to hear the story of this monster's
discovery.rwg@RUSSIAN.SPA.Symbolics.COM (Bill Gosper) (03/29/91)
I've forwarded this to rcs@la.tis.com.
Date: Thu, 28 Mar 1991 11:20-0500
From: Allan C. Wechsler <ACW@YUKON.SCRC.Symbolics.COM>
Date: Wed, 27 Mar 1991 12:51 EST
From: Paul Crowley <aipdc@castle.edinburgh.ac.uk>
What's the simplest known pattern that has no parent?
Winning Ways p. 829 gives:
xxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxx
x x x x x x xxxx xx xxx xxx xx xx
xxxxxxxxxxxxx x x xxx xxx xxx xx
x x x x x x xx xxxxx xxx xxx xxxx
x x x x x x xxx x xxx xxx xx x x
xxxxxxxxxxxxxx xxxx xxx xxx xxxxx
x x x x x x xxx xxxx xxx xxx x x
x x x x x x x x x xx xxx xxx x xx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
I understand Schroeppel was in the group that discovered this; I don't
know his net address but I've CC'd Gosper and perhaps he'd be willing to
forward to Schroeppel our request to hear the story of this monster's
discovery.
I think Roger Banks wrote the "ataviser" program, and some subset of Banks,
Schroeppel, Mike Speciner, and Mike Beeler "manually" guided a marathon
tree search.
About a year and a half ago, Schroeppel and Hickerson found a bunch of
patterns with very small predecessor counts. These are used as modules
in existence proofs for GOE's within various rectangles, some quite cozy.
Rich should know the current record.xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) (03/29/91)
ACW@YUKON.SCRC.Symbolics.COM (Allan C. Wechsler) writes: > Paul Crowley <aipdc@castle.edinburgh.ac.uk> writes: >> What's the simplest known pattern that has no parent? > Winning Ways p. 829 gives: > xxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxx > x x x x x x xxxx xx xxx xxx xx xx > xxxxxxxxxxxxx x x xxx xxx xxx xx > x x x x x x xx xxxxx xxx xxx xxxx > x x x x x x xxx x xxx xxx xx x x > xxxxxxxxxxxxxx xxxx xxx xxx xxxxx > x x x x x x xxx xxxx xxx xxx x x > x x x x x x x x x xx xxx xxx x xx > xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx > I understand Schroeppel was in the group that discovered this; I don't > know his net address but I've CC'd Gosper and perhaps he'd be willing > to forward to Schroeppel our request to hear the story of this > monster's discovery. This is probably a bit of a vague question (no "probably" about it, actually), but have there been enough "Garden of Eden" patterns discovered to allow a statement as to whether there is anything in common "interesting" about their subsequent histories? Or is this the only thing they have in common? I guess what I'm after is whether the constraints necessary to have no past are also constraints that create an interesting future. Kent, the man from xanth. <xanthian@Zorch.SF-Bay.ORG> <xanthian@well.sf.ca.us>
ACW@YUKON.SCRC.Symbolics.COM (Allan C. Wechsler) (03/30/91)
Date: Fri, 29 Mar 1991 06:40 EST
From: xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan)
ACW@YUKON.SCRC.Symbolics.COM (Allan C. Wechsler) writes:
> Paul Crowley <aipdc@castle.edinburgh.ac.uk> writes:
>> What's the simplest known pattern that has no parent?
> Winning Ways p. 829 gives:
> xxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxx
> x x x x x x xxxx xx xxx xxx xx xx
> xxxxxxxxxxxxx x x xxx xxx xxx xx
> x x x x x x xx xxxxx xxx xxx xxxx
> x x x x x x xxx x xxx xxx xx x x
> xxxxxxxxxxxxxx xxxx xxx xxx xxxxx
> x x x x x x xxx xxxx xxx xxx x x
> x x x x x x x x x xx xxx xxx x xx
> xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
> I understand Schroeppel was in the group that discovered this; I don't
> know his net address but I've CC'd Gosper and perhaps he'd be willing
> to forward to Schroeppel our request to hear the story of this
> monster's discovery.
This is probably a bit of a vague question (no "probably" about it,
actually), but have there been enough "Garden of Eden" patterns
discovered to allow a statement as to whether there is anything in
common "interesting" about their subsequent histories? Or is this
the only thing they have in common?
I guess what I'm after is whether the constraints necessary to have
no past are also constraints that create an interesting future.
A fascinating notion. Unfortunately, the GoE pattern shown above dies
off entirely in exactly two generations. This is due to the extremely
dense interior.
When you try to build parentless patterns, you naturally begin with
smaller "modules" that have very few predecessors. You then join these
in "awkward" ways in the hopes that border constraints will further
reduce the number of possible parents.
A single live cell has 140 predecessors in a 3x3 square, while a single
dead cell has 372 predecessors. So the most promising 1x1 module is a
live cell, not a dead one. This suggests that orphan patterns are
likely to have fairly high density.
Another way to say this is that typical daughter patterns have fairly
low density, so we'd expect orphans to have high density.
If these generalizations are true, then parentless patterns are all
likely to die quickly.
Of course, you can put an R pentomino near an established orphan and
create another pattern that is also an orphan but will perk along for a
long time. But I suppose we are talking about "minimal" orphans --
orphans that cease to be orphans if any part of the pattern is removed.