on Life (and Death)
Allan C. Wechsler
Date: Wed, 27 Mar 1991 12:51 EST
From: Paul Crowley <ai...@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.
Bill Gosper
Date: Thu, 28 Mar 1991 11:20-0500
From: Allan C. Wechsler <A...@YUKON.SCRC.Symbolics.COM>
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.
Kent Paul Dolan
> Paul Crowley <ai...@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.
<xant...@Zorch.SF-Bay.ORG> <xant...@well.sf.ca.us>
Allan C. Wechsler
Date: Fri, 29 Mar 1991 06:40 EST
From: xant...@zorch.SF-Bay.ORG (Kent Paul Dolan)
> Paul Crowley <ai...@castle.edinburgh.ac.uk> writes:
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.