Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!sdd.hp.com!spool.mu.edu!uunet!mcsun!hp4nl!tuegate.tue.nl!gem!angelo
From: angelo@gem.stack.urc.tue.nl (Angelo Wentzler)
Newsgroups: comp.theory.cell-automata
Subject: on Life (and Death)
Message-ID: <180@gem.stack.urc.tue.nl>
Date: 18 Mar 91 17:51:07 GMT
Article-I.D.: gem.180
Organization: Stack, Eindhoven University of Technology, The Netherlands
Lines: 34

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