Smallest Garden of Eden
In search of the smallest Garden of Eden
Garden of Eden
In a cellular automaton, a Garden of Eden configuration is a configuration that cannot appear on the lattice after one time step, no matter what the initial configuration. In other words, these are the configurations with no predecessors. They resemble the concept of the Garden of Eden in Abrahamic religions, which was created out of nowhere, hence the name. According to Moore (1962), this name was coined by John Tukey in the 1950s. A Garden of Eden is a configuration of the whole lattice (usually a one- or two-dimensional infinite square lattice). Each Garden of Eden configuration contains at least one finite pattern (an assignment of states to a finite subset of the cells) that has no predecessor regardless of how the surrounding cells are filled. Such a pattern is called an orphan. Alternatively, an orphan is a finite pattern such that each configuration containing that pattern is a Garden of Eden.
Source: Wikipedia
The cellular automaton which we are using is the Conway's Game of Life.
Orphans
A related concept to Gardens of Eden is that of orphans, which are finite patterns that can not occur as part of the evolution of another pattern. That is, they are Gardens of Eden that can be extended in any way to form other Gardens of Eden.
Source: conwaylife.com Wiki
Our orphans
Orphan 1
We have found an orphan with smaller dimensions and fewer defined cells than the ones currently known on 14 December 2011. This orphan fits within a 10x10 bounding box and has only 92 defined cells. Our experiments also show that this is the smallest possible quarter-symmetric orphan.
Figure
In the figure we have 3 kinds of cells:
- black cells, which are alive.
- white cells, which are dead.
- gray cells, which could have both values (don't care).
Golly
Orphan 1 in Golly code:
Download Golly here
Stats
Some statistics of orphan 1:
- 56 alive cells
- 36 dead cells
- 92 defined cells
- 60.9% alive cells
Orphan 2
We have found an orphan with a lower density than the ones currently known on 15 January 2012. This orphan has a density of 0.378151. It also matches the record for fewest number of alive cells which is 45.
Figure
In the figure we have 3 kinds of cells:
- black cells, which are alive.
- white cells, which are dead.
- gray cells, which could have both values (don't care).
Golly
Orphan 2 in Golly code:
Download Golly here
Stats
Some statistics of orphan 2:
- 45 alive cells
- 74 dead cells
- 119 defined cells
- 37.8151% alive cells
Orphan 3
We have found an orphan with a lower density than the ones currently known on 22 January 2012. This orphan has a density of 0.320261.
Figure
In the figure we have 3 kinds of cells:
- black cells, which are alive.
- white cells, which are dead.
- gray cells, which could have both values (don't care).
Golly
Orphan 3 in Golly code:
Download Golly here
Stats
Some statistics of orphan 3:
- 49 alive cells
- 104 dead cells
- 153 defined cells
- 32.0261% alive cells
Lower bound
Our experiments show that there exist no orphan within a 6x6 bounding box, so all Game of Life patterns bounded by a 6x6 rectangle have a predecessor.
Who we are
We are Marijn Heule, Christiaan Hartman, Kees Kwekkeboom and Alain Noels from the TU Delft. Marijn Heule is a postdoc within the Algorithmics Group. Christiaan Hartman, Kees Kwekkeboom and Alain Noels are Master students embedded systems.
Orphan records webpage
Achim Flammenkamp updates the records for newly found orphans on his webpage. You can click here for his general webpage about orphans and click here for his page about our orphans.
Contact
Please click here to e-mail us.
ConwayLife Forum
Join the discussion on our orphan on the ConwayLife forum by clicking here.
