Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!uwm.edu!bionet!agate!ucbvax!bloom-beacon!dont-send-mail-to-path-lines
From: ACW@YUKON.SCRC.Symbolics.COM (Allan C. Wechsler)
Newsgroups: comp.theory.cell-automata
Subject: on Life (and Death)
Message-ID: <19910320160714.2.ACW@PALLANDO.SCRC.Symbolics.COM>
Date: 20 Mar 91 16:07:00 GMT
References: <180@gem.stack.urc.tue.nl>
Sender: daemon@athena.mit.edu (Mr Background)
Distribution: inet
Organization: The Internet
Lines: 42


    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. Wechsler