Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!sol.ctr.columbia.edu!spool.mu.edu!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: <19910329181900.0.ACW@PALLANDO.SCRC.Symbolics.COM>
Date: 29 Mar 91 18:19:00 GMT
Article-I.D.: PALLANDO.19910329181900.0.ACW
References: <1991Mar29.114043.9951@zorch.SF-Bay.ORG>
Sender: tytso@athena.mit.edu (Theodore Y. Ts'o)
Distribution: inet
Organization: The Internet
Lines: 60


    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.