State wrt "Garden of Eden"in Conway's "Game of Life"
acd
is known
that none exists up to size 5x5.
I have a apparently new method to investigate the existence of GoE
configurations and
have proven that none exists until size 7x7
This result is of course trustworthy only modulo programming errors.
I will only be sure I do not have any serious ones when I have found
the first known GoE configuration.
Is that a progress or is Wikipedia not up to date?
Besides, the program took less than an hour on my thinkpad and I have
not yet used all
methods I have available. So chances to got larger sizes are good.
Andreas
Dave Greene
> Wikipedia lists the smallest known GoE in Life to be 11x12 and that it
> is known that none exists up to size 5x5.
Where does Wikipedia mention the 5x5 lower limit? I didn't see it on
a quick scan of the main article and various links.
I think Achim Flammenkamp's website probably has the most recent
information on Conway's Life GOEs (since he has done so much of the
research himself):
http://wwwhomes.uni-bielefeld.de/achim/orphan.html
"Intensive computations have established the fact that all Game of
Life patterns bounded by a 6x5 rectangle have a predecessor."
> I have a apparently new method to investigate the existence of GoE
> configurations and have proven that none exists until size 7x7
> This result is of course trustworthy only modulo programming errors.
> I will only be sure I do not have any serious ones when I have found
> the first known GoE configuration.
Would that mean that, according to your program, all of the 500
trillion 7x7 patterns have predecessors? Or just that everything
smaller than that (6x7?) has a predecessor?
> Is that a progress or is Wikipedia not up to date?
As far as I know, even a definite result for the 6x6 case would be
progress. The most recent investigation of GoEs that I know about was
some interesting work that Donald Knuth recently did in passing for
his upcoming Volume 4 of _The Art of Computer Programming_, using
binary decision diagrams.
He wrote the following handy summary (except that items like "$m\timesn
$" have been replaced here by "MxN" -- for which typographical heresy
I take full responsibility):
| ... it's important to clarify a subtle distinction between
| a Garden of Eden and an "orphan". An orphan is a set of
| cell states that cannot arise after one step of Life; a Garden
| of Eden is an orphan that includes every cell of the plane.
| Furthermore, an MxN orphan is an orphan whose cells
| are defined only inside an MxN rectangle;
| an MxN Garden of Eden is a Garden of Eden for which
| all cells are dead outside of such a rectangle.
|
| It is known that there are no 5x6 orphans. But I do not
| believe anybody has proved even that there are no 5x5
| Gardens of Eden. To do that, you'd need to establish the
| existence of predecessors that not only match the states
| inside any given 5x5, they also kill off everything
| outside of the square.
|
| I could probably write a program in a few hours that would take
| all of the 138,626 pseudo-gardens and find a valid predecessor
| for them; probably I wouldn't need to go further than 9x9
| or 11x11. I haven't time to do that, but my example above
| shows that such a program must be run before anybody can claim
| that 5x5 Gardens of Eden do not exist. Such a claim is
| much stronger than claiming that 5x5 orphans do not exist.
|
| Indeed, I believe there is no known example of a rectangular
| Garden of Eden that is not an orphan; yet I believe it is
| likely that such Gardens of Eden do exist. I almost found
| such an example by combining two instances of Achim
| Flammenkamp's 10x13 rectangle that has exactly one
| 12x15 predecessor.
So it sounds as if what you're working on is the existence problem for
6x6 or 7x7 orphans, not necessarily Gardens of Eden per se. Can you
explain your new method in any more detail? In particular, is it a
useful constructive method -- i.e., might it provide a quick way to
find, or even enumerate, predecessors of any given pattern?
Keep the cheer,
Dave Greene
Dave Greene
> ... some interesting work that Donald Knuth recently did in passing for
> his upcoming Volume 4 of _The Art of Computer Programming_, using
> binary decision diagrams.
>
The full text can be found at
The short quote I gave mentioned a specific example, which was a 7x7
pattern that produces a 5x5 child pattern, but that cannot be extended
by adding any number of cells beyond the 7x7 boundary to produce
_only_ the 5x5 child with dead cells everywhere else. The relevant
section is about four-fifths of the way down the file.
acd
>
> > I have a apparently new method to investigate the existence of GoE
> > configurations and have proven that none exists until size 7x7
> > This result is of course trustworthy only modulo programming errors.
> > I will only be sure I do not have any serious ones when I have found
> > the first known GoE configuration.
>
> Would that mean that, according to your program, all of the 500
> trillion 7x7 patterns have predecessors? Or just that everything
> smaller than that (6x7?) has a predecessor?
I compute the other way round:
I count the number of images that the function from 9x9 to 7x7
has.
Of course I do not "really" count but have a method to determine the
size of the function image efficiently.
> As far as I know, even a definite result for the 6x6 case would be
> progress. The most recent investigation of GoEs that I know about was
> some interesting work that Donald Knuth recently did in passing for
> his upcoming Volume 4 of _The Art of Computer Programming_, using
> binary decision diagrams.
That is exactly what I am using, BDD-based image size computation,
the base algorithm is known and published in textbooks,
but it is not enough.
>
> He wrote the following handy summary (except that items like "$m\timesn
> $" have been replaced here by "MxN" -- for which typographical heresy
> I take full responsibility):
>
> | ... it's important to clarify a subtle distinction between
> | a Garden of Eden and an "orphan". An orphan is a set of
> | cell states that cannot arise after one step of Life; a Garden
> | of Eden is an orphan that includes every cell of the plane.
> | Furthermore, an MxN orphan is an orphan whose cells
> | are defined only inside an MxN rectangle;
> | an MxN Garden of Eden is a Garden of Eden for which
> | all cells are dead outside of such a rectangle.
> |
> | It is known that there are no 5x6 orphans. But I do not
> | believe anybody has proved even that there are no 5x5
> | Gardens of Eden. To do that, you'd need to establish the
> | existence of predecessors that not only match the states
> | inside any given 5x5, they also kill off everything
> | outside of the square.
Ok, so it is orphans.
I was not aware of this distinction.
> |
> | I could probably write a program in a few hours that would take
> | all of the 138,626 pseudo-gardens and find a valid predecessor
> | for them; probably I wouldn't need to go further than 9x9
> | or 11x11. I haven't time to do that, but my example above
> | shows that such a program must be run before anybody can claim
> | that 5x5 Gardens of Eden do not exist. Such a claim is
> | much stronger than claiming that 5x5 orphans do not exist.
> |
> | Indeed, I believe there is no known example of a rectangular
> | Garden of Eden that is not an orphan; yet I believe it is
> | likely that such Gardens of Eden do exist. I almost found
> | such an example by combining two instances of Achim
> | Flammenkamp's 10x13 rectangle that has exactly one
> | 12x15 predecessor.
>
> So it sounds as if what you're working on is the existence problem for
> 6x6 or 7x7 orphans, not necessarily Gardens of Eden per se. Can you
> explain your new method in any more detail? In particular, is it a
> useful constructive method -- i.e., might it provide a quick way to
> find, or even enumerate, predecessors of any given pattern?
>
As mentioned, yes I use BDD.
I intend to publish this, but still can give a sketch here,
(or should now):
With a BDD you can efficiently find the size of the fulfilling set of
a boolean n-to-1 function,
because you can get an enumeration of disjoint cubes.
With that, assuming you have an m-to-n bit function represented as
BDD,
you can represent it as relation:
r = {(a,b)| a=f(b)}
that is you add variables and than create a new boolean function with n
+m inputs
by doing bitwise compares of the a-variables with the result-functions
for f (depending on inputs b).
After that you do an exist-reduction of the b-variables,
which gives you a function r' which only depends on the a-variables
which represent the image.
This function is '1' exactly for those patterns which can arise as a
function value of f.
Now, if we try this with GoL directly, this seems to be horribly
slow.
I did not measure, a first trial did not finish after one night.
I probably should try with very small examples.
Therefore I combine the rectangle piece by piece:
If I have a function into a product set
f: B \mapsto A1xA2
I can first generate the relation (as before) on projected functions
f1 B \mapsto A1
and f2 B \mapsto A2
And create the relations for them,
r1 and r2
(as before
r1 = {(a,b)| a=f1(b)},
r2 = {(a,b)| a=f1(b)},
Now, the relation for our searched function f is the AND combination
of r1 and r2:
r((a1,a2),b) = {((a1,a2),b)| a1=f1(b) AND a2=f2(b)}=
r1 AND r2.
This AND is much easier to compute in a BDD than directly constructing
f.
Therefore, I have created a "little" language, consisting of
operations
create, shift , join, reduce and count.
They operate on rectangular relations of input and output variables,
represented as relation
for the given cellular automaton.
create - creates the relation for a rectangular image set.
shift - renames the variables in an existing relation such that it
applies to other input variables
corresponding to (geometric) movement of the image set.
join - joins two elements, that is it does the AND as described
before, and also keeps track of what the input and output
variable sets are.
reduce - This does the exist-quantifying removal of the input
variables, also partially:
As I do not need the outside input variables anymore I can
reduce them before I do a join.
count - Assuming that all inputs have been removed by use of reduce, I
can count the image set size of the remaing relation.
If - after full input reduction - the remaining function is
not constant true, we know that we have
found an orphan, there is a configuration which does not
appear as image.
This step is currently the weakest in my implementation: I
count into 64-bit integers and output the result as number,
and this will therefore fails for more than 2^64 cell images.
But it is of course easy to fix, I can check whether the function is
constant true, and if not, give a cube that is not in the image.
I have not yet experimented with reduce a lot.
The idea - as mentioned is to remove inputs as early as possible to
reduce the complexity of the relation.
So, for 6x6 It works something like:
C00=create (0,0)
S01=Shift(C00,(0,1))
J01=Join(C00,S01)
S03=Shift(C00,(0,2))
J03=Join(S03,J01)
S03=Shift(J03,(0,3))
J06=Join(J03,S03)
and then the same horizontally (shifts in other direction).
In this way I build larger and larger regions.
At the end, one big reduce and one count.
The way this is described, you could do some steps in parallel,
but it is not worth it: the biggest complexity is alone in the last
join.
I hope to improve it by inserting reduces before, so instead of
combining
two rectangles 3x7 and 4x7 image variables and 5x9 and 6x9 origin
variables
(which overlap!),
I could remove variables to the left and right and
join two rectangles with only 3x9 origin variables each.
Saving 45 input variables in our relations before we do the join
should help a lot.
I have implemented the method in C++ using Cudd (BDD library by Fabio
Somenzi, Boulder)
and Xerces-C (I represent this "program" shown before as XML).
I also plan to do some extensions:
searching for symmetric orphans, for stills, periodic pattern, etc.
can all be done using the
same method of starting with small rectangles, represented as BDD
relation and combining them to larger structures.
In fact, the difference in code is quite small, only the create and
reduce.
Andreas