proof for garden of eden in GOL ?
Mariano Domínguez Molina
I found in the Bibliography of Conway's Game of Life, two patterns with
no ancestors.
Where can I find a proof of these garden of eden patterns, or how they
were built ?.
Thanks in advance.
Tim Tyler
: I found in the Bibliography of Conway's Game of Life, two patterns with
: no ancestors.
: Where can I find a proof of these garden of eden patterns, or how they
: were built ?.
Proving that a particular configuration of a irreversible cellular
automata is, in fact, a 'garden of eden' is, in general, an example of a
very difficult problem.
Typically, proof involves an exhaustive search through all the
possible predecessors.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ t...@cryogen.com
<<Press here>> for static discharge.
Mariano Domínguez Molina
Tim Tyler wrote:
> Typically, proof involves an exhaustive search through all the
> possible predecessors.
> --
Hello:
yes, when you want to proof that a certain pattern is a garden of eden,
an exhaustive search might work, but the smallest GOL Garden of Eden has
size 14x14, that means you have to search in all the possible patterns
of 17x17. o(2^n+2^2) for nxn patterns.
This is too much computational complexity for a brute-force calculus.
I've found in papers the subset diagrams can generate evolution-excluded
words in the elementary automata, but the extension to 2D is not clear.
----------
Greetings
Mariano
David Eppstein
> yes, when you want to proof that a certain pattern is a garden of eden,
> an exhaustive search might work, but the smallest GOL Garden of Eden has
> size 14x14, that means you have to search in all the possible patterns
> of 17x17. o(2^n+2^2) for nxn patterns.
> This is too much computational complexity for a brute-force calculus.
No it isn't. At least not if you include some intelligence in your
brute force. Theoretically, the complexity of finding a predecessor for
a given pattern only needs to be something like 2^(3w), where w is the
width of the pattern. But in practice, it's even less than that. Check
out lifesrc (http://www.cs.jhu.edu/~callahan/lifesearch.txt or
http://www.canb.auug.org.au/~dbell/programs/lifesrc-3.5.tar.gz), a
program which uses a backtracking search to find life patterns of
various sorts including predecessors of a given pattern.
As an example of the size of pattern these search programs can find,
here's a large spaceship moving at speed 2c/5 in HighLife (B36/S23).
(Your programs probably already understand this encoding, but if not:
the b's represent spaces, the o's represent live cells, the dollars
represent the start of a new line, and a number before something indicates
to repeat it that many times.)
x = 19, y = 43, rule = B36/S23
4b2o7b2o$5bo7bo$8bobo$4bobobobobobo$3bo3bo3bo3bo$4bobo5bobo$5bo7bo2$8b
3o$9bo$6b2obob2o$8b3o$6bo2bo2bo$6bobobobo$2bo5b3o5bo$2bob3obobob3obo$
2bo3b2obob2o3bo$3b3o2b3o2b3o$4bobo2bo2bobo$6b2obob2o$9bo$7bo3bo$9bo$7b
2ob2o$6bo2bo2bo$6b2obob2o$9bo$7b2ob2o$7b2ob2o$4b2o3bo3b2o$5bo7bo$4bo9b
o$4b2o7b2o2$3bobo7bobo$2bobo9bobo$4bo9bo$3o3bo5bo3b3o$b2ob2o7b2ob2o$2b
2o4bobo4b2o$3b3o7b3o$8b3o$9bo!
I found this with a different search program than lifesrc
(http://www.ics.uci.edu/~eppstein/ca/gfind.c) but it should be possible
for a garden-of-eden testing routine to work even faster (or for larger
sizes) than the search for this sort of pattern, because it only has one
generation of pattern to look for rather than (in this case) five.
--
David Eppstein UC Irvine Dept. of Information & Computer Science
epps...@ics.uci.edu http://www.ics.uci.edu/~eppstein/
Tim Tyler
: Tim Tyler wrote:
:> Typically, proof involves an exhaustive search through all the
:> possible predecessors.
: yes, when you want to proof that a certain pattern is a garden of eden,
: an exhaustive search might work, but the smallest GOL Garden of Eden has
: size 14x14, that means you have to search in all the possible patterns
: of 17x17. o(2^n+2^2) for nxn patterns.
: This is too much computational complexity for a brute-force calculus.
If examining 2^256 life patterns is beyond your scope ;-) the only other
reference I have is from William Poundstone's "The Recursive Universe".
This describes briefly the discovery of the first GOL GOE by Roger Banks,
saying: "[he] used sophisticated mathematical techniques to prove that a
certain 9-by-33 rectangular pattern is itself a Garden-of-Eden pattern."
That 9x33 pattern is widely availabe on the net (as "EDEN.LIF"). It
exhibits strange regularities (which aren't present in the 14x14 GOE)
- which, perhaps, are stigmata of the construction technique.
All the GOEs I've seen have been rectangular - including the smallest
known. I can't think of any terribly good reason why GOEs should be
rectangular - perhaps this is an artefact of the search techniques used.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ t...@cryogen.com
Recursive defintion: see definition, recursive.