Garden of Eden

From LifeWiki
(Redirected from Gardens of Eden)
Jump to navigation Jump to search

A Garden of Eden is a pattern that has no parents and thus can only occur in generation 0. The term was first used in connection with cellular automata by John W. Tukey, many years before Conway's Game of Life was conceived. It was known from the start that Gardens of Eden exist in Life because of a theorem by Edward Moore that guarantees their existence in a wide class of cellular automata.

Garden of Eden theorem

The Garden of Eden theorem was proved by Edward Moore and John Myhill pre-1970 and shows that a wide class of cellular automata must contain Garden of Eden patterns. Of particular interest is that Conway's Game of Life falls into this class, and thus Gardens of Eden were known to exist right from the day it was conceived.

Statement of the theorem

A finite pattern (or finite configuration) is a pattern with a finite number of cells. A cellular automaton is said to be injective over finite patterns if no two distinct finite patterns map into the same finite pattern. It is said to be surjective if every pattern is mapped to by some other pattern. Thus, by definition a cellular automaton contains Gardens of Eden if and only if it is not surjective.

The Garden of Eden theorem states that the class of surjective cellular automata and those which are injective over finite configurations coincide. In other words, a cellular automaton has a Garden of Eden if and only if it has two different finite configurations that evolve into the same configuration in one step.

As a corollary, every injective cellular automaton (i.e., one with one-to-one global mapping for both finite and infinite patterns) is surjective and hence bijective. However, surjective cellular automata do not need to be injective over infinite patterns (and thus need not be injective in general).

Application to Conway's Game of Life

The theorem applies to Conway's Game of Life because it is easy to find two different finite patterns that are mapped into the same configuration. The configuration in which every cell is dead, and the one in which exactly one cell is alive both lead to the one in which every cell is dead. The Garden of Eden theorem then implies that there must exist a Garden of Eden pattern.

Pre-block and grin are both parents of the block. The Garden of Eden theorem thus says that Gardens of Eden exist in 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.

Explicit examples

Several Gardens of Eden and orphans have been constructed, the first by Roger Banks et al. at MIT in 1971. It had a bounding box of size 33×9 and had 226 cells. Jean Hardouin-Duparc found the second and third orphans by computer search in 1973, which had bounding boxes of size 122×6 and 117×6. It was long suspected that no height-5 Gardens of Eden exist, but in April 2016, Steven Eker found a Garden of Eden fitting inside a 5×83 bounding box.[1] Eker also proved that any Garden of Eden must have a height greater than 3. It is not known if any height-4 Gardens of Eden exist.

Many smaller Gardens of Eden have been found in more recent years. Garden of Eden 2 was found by Achim Flammenkamp in 1991, contained 143 cells, and had a bounding box of size 14×14. Garden of Eden 3 was found by Achim Flammenkamp in 2004, contained 81 cells, and had a bounding box of size 13×12. The smallest known Garden of Eden for about five years was Garden of Eden 4,[2] which was also found by Achim Flammenkamp in 2004. It contained 72 cells and had a bounding box of size 12×11. Smaller Gardens of Eden were subsequently found, including Garden of Eden 5 and Garden of Eden 6, which contains 56 live cells and a bounding box of 10×10 and was found on December 14, 2011. For the smallest Garden of Eden currently known, refer to the table below.

Computer searches have revealed that there are no Gardens of Eden contained within a 6×6 bounding box.[3]

Many Gardens of Eden found by Nicolay Beluchenko in 2009
Download RLE: click here

Records

The following is a list of Gardens of Eden. Numbers marked red are records. Width of the bounding box is more than or equal to height.

Year Author Bounding box width × height Orphan Population Density Symmetry Pattern Note
1971 Roger Banks et al. 33 × 9 = 297
size = 297
226 0.7609 C1
x = 33, y = 9, rule = B3/S23 33o$2obob3ob3ob2obobobobobobobobobo$obob3ob3ob4ob3obobobobobobo$5ob3ob 3ob4ob14o$obob2ob3ob3obob3obobobobobobo$4ob3ob3ob5ob2obobobobobobo$b2o b3ob3ob3obobob13o$2ob2ob3ob3ob2ob4obobobobobobo$18ob14o! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] #C [[ THUMBNAIL THUMBSIZE 4 ZOOM 16 ]]
(click above to open LifeViewer)
RLE: here Plaintext: here
Truncated form
Garden of Eden 1, which is still a Garden of Eden even after removing the five rightmost columns[1]
1973 Jean Hardouin-Duparc 122 × 6 = 732 size = 732 576 0.7869 - - not a GoE, one predecessor[1]
1973 Jean Hardouin-Duparc 117 × 6 = 702 - - - - - [1]
1991 Achim Flammenkamp 14 × 14 = 196
size = 196
143 0.7296 C1
x = 14, y = 14, rule = B3/S23 2obobobob2obo$ob3ob3ob2obo$4ob3ob2obo$3obobobob4o$b3obob3ob2o$7ob4obo$ bobob8o$ob3ob2obobobo$6ob6o$ob2ob5obobo$3ob9o$b3obobobob3o$3obobobob2o bo$ob12o! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] #C [[ THUMBNAIL THUMBSIZE 4 ZOOM 16 ]]
(click above to open LifeViewer)
RLE: here Plaintext: here
Garden of Eden 2[1]
2004 Achim Flammenkamp 13 × 12 = 156
size = 136
size = 134 (alternative form from Nicolay Beluchenko, 2006)
81 0.5956 C1
x = 13, y = 12, rule = B3/S23 2bob3o$2obob5obo$obob2obobo$b4obob3o$obob2ob3obo$b3ob2obobo$2bo3b3o2b 2o$bob2obobob2o$3ob4obobo$bob4o3bo$bobob2o2bo$b2obo2b2o2bo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] #C [[ THUMBNAIL THUMBSIZE 4 ZOOM 16 ]]
(click above to open LifeViewer)
RLE: here Plaintext: here
Garden of Eden 3[1]
2004 Achim Flammenkamp 12 × 11 = 132
size = 113
72 0.6372 C1
x = 12, y = 11, rule = B3/S23 bob2ob2o2bo$2bob3ob3o$2b2ob3obobo$bob3ob3obo$5o2b4o$b2ob3obo2bo$b3obob o2bo$b2ob3o2b2o$ob3ob3obo$o2b2o2bobobo$10bo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] #C [[ THUMBNAIL THUMBSIZE 4 ZOOM 16 ]]
(click above to open LifeViewer)
RLE: here Plaintext: here
Garden of Eden 4[2]
2004 Achim Flammenkamp 13 × 10 = 130 - - - C1 - not a GoE, one unique predecessor[2]
2009 Nicolay Beluchenko 11 × 11 = 121
size = 109
69 0.6330 C4_1
x = 11, y = 11, rule = B3/S23 b3o2b2o$b2obobob3o$b3o2b5o$obobobobobo$4obobobo$4b3o$bobobob4o$obobobo bobo$5o2b3o$3obobob2o$3b2o2b3o! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] #C [[ THUMBNAIL THUMBSIZE 4 ZOOM 16 ]]
(click above to open LifeViewer)
RLE: here Plaintext: here
Flower of Eden, or Garden of Eden 5[4]
2009 Nicolay Beluchenko 11 × 11 = 121 size = 113 59 0.5221 C1 - [4]
2009 Nicolay Beluchenko 11 × 11 = 121 size = 110 49 0.4455 D2_x - [5]
2009 Nicolay Beluchenko 13 × 11 = 143 size = 139 58 0.4173 C1 - [5]
2009 Nicolay Beluchenko 11 × 11 = 121 size = 115 47 0.4087 D2_x - [6]
2009 Nicolay Beluchenko 11 × 11 = 121 size = 107 51 0.4766 D2_x - [6]
2009 Nicolay Beluchenko 11 × 11 = 121
size = 113
45 0.3982 D2_x
x = 11, y = 11, rule = B3/S23 3b2o3bo$2bo2bobobo$bobo2bo3bo$obobo2bobo$o2bobo2bo$bo2b3o2bo$2bo2bobo 2bo$bobo2bobobo$o3bo2bobo$bobobo2bo$2bo3b2o! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] #C [[ THUMBNAIL THUMBSIZE 4 ZOOM 16 ]]
(click above to open LifeViewer)
RLE: here Plaintext: here
45-cell Garden of Eden, the smallest known in terms of population[7]
2009 Nicolay Beluchenko 12 × 12 = 144 size = 129 50 0.3876 C1 - [7]
2011 Marijn Heule et al. 11 × 11 = 121 size = 93 65 0.6989 D8_1 - almost Garden of Eden 6
2011 Marijn Heule et al. 11 × 11 = 121 size = 119 45 0.3781 D8_1 - almost Garden of Eden 6
2011 Marijn Heule et al. 13 × 13 = 169 size = 153 49 0.3203 D8_1 - [8]
2011 Marijn Heule et al. 10 × 10 = 100
size = 92
56 0.6087 C4_4
x = 10, y = 10, rule = B3/S23 bob3obo$2bobobo2bo$ob3o2b2o$bob5obo$o2bo2b4o$4o2bo2bo$ob5obo$b2o2b3obo $o2bobobo$2bob3obo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] #C [[ THUMBNAIL THUMBSIZE 4 ZOOM 16 ]]
(click above to open LifeViewer)
RLE: here Plaintext: here
Garden of Eden 6[9][10], ranked third place in the Pattern of the Year 2011 competition on ConwayLife.com forums, behind the lobster and the fully universal Turing machine.[11]
2015 Steven Eker 11 × 9 = 99 size = 99 66 0.6667 C1 - [12]
2016 Steven Eker 12 × 8 = 96
size = 96
57 0.5938 C1
x = 12, y = 8, rule = B3/S23 o2b2obo2b3o$b2o2b2obobo$obobo2bobobo$b4o2b2o2bo$o3b3ob4o$2obobo2bob2o$ obo2b3obobo$b4obob4o! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] #C [[ THUMBNAIL THUMBSIZE 4 ZOOM 16 ]]
(click above to open LifeViewer)
RLE: here Plaintext: here
Garden of Eden 8×12, the smallest known in terms of bounding box[12]
2016 Steven Eker 83 × 5 = 415 size = 410 284 0.6927 C1 - [1]
2016 Steven Eker 45 × 5 = 225
size = 223
139 0.6233 D2_+1
x = 45, y = 5, rule = B3/S23 2obobo2bob3obo2b3ob7o2b6o2bobobobo$b2obob2obobobobobob3obobobobobobob 3obobobo$2b2ob2o2b4o2b6o2b6o2b5ob5obo$b2obob2obobobobobob3obobobobobob ob3obobobo$2obobo2bob3obo2b3ob7o2b6o2bobobobo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] #C [[ THUMBNAIL THUMBSIZE 4 ZOOM 16 WIDTH 800 ]]
(click above to open LifeViewer)
RLE: here Plaintext: here
Garden of Eden 5×45, the shortest known with the smallest height[13]
2016 Steven Eker 9 × 11 = 99 size = 89 55 0.6180 C1 - [13]
2017 Steven Eker 9 × 11 = 99
size = 88
50 0.5682 C1
x = 11, y = 9, rule = B3/S23 2b2ob3obo$bo2bobobo$ob3o2b3o$bobobo2bobo$b3o2b2o2bo$2o3b2o2bo$obobob3o $o2bobo2bo$b3o2b4o! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] #C [[ THUMBNAIL THUMBSIZE 4 ZOOM 16 ]]
(click above to open LifeViewer)
RLE: here Plaintext: here
Garden of Eden 11, with the smallest known orphan[14]

See also

References

  1. 1.0 1.1 1.2 1.3 1.4 1.5 1.6 Achim Flammenkamp (January 27, 2017). "Garden of Eden / Orphan". Achim's Game of Life Page. Retrieved on December 24, 2020.
  2. 2.0 2.1 2.2 Achim Flammenkamp (December 1, 2009). "Garden of Eden / Orphan". Achim's Game of Life Page. Retrieved on December 24, 2020.
  3. Adam P. Goucher (January 14, 2012). "Gardens of Eden". Game of Life News. Retrieved on June 18, 2012.
  4. 4.0 4.1 Achim Flammenkamp (December 1, 2009). "Garden of Eden / Orphan". Achim's Game of Life Page. Retrieved on December 24, 2020.
  5. 5.0 5.1 Achim Flammenkamp (December 1, 2009). "Garden of Eden / Orphan". Achim's Game of Life Page. Retrieved on December 24, 2020.
  6. 6.0 6.1 Achim Flammenkamp (December 21, 2009). "Garden of Eden / Orphan". Achim's Game of Life Page. Retrieved on December 24, 2020.
  7. 7.0 7.1 Achim Flammenkamp (December 21, 2009). "Garden of Eden / Orphan". Achim's Game of Life Page. Retrieved on December 24, 2020.
  8. Achim Flammenkamp (February 2, 2012). "Garden of Eden / Orphan". Achim's Game of Life Page. Retrieved on December 24, 2020.
  9. Achim Flammenkamp (December 17, 2011). "Garden of Eden / Orphan". Achim's Game of Life Page. Retrieved on December 24, 2020.
  10. Marijn J. H. Heule et al. (August 9, 2013). "Symmetry in Gardens of Eden". Electron. J. Comb.. Retrieved on January 5, 2021.
  11. beebop (February 28, 2012). Patterns of the Year 2011 (discussion thread) at the ConwayLife.com forums
  12. 12.0 12.1 Achim Flammenkamp (April 13, 2016). "Garden of Eden / Orphan". Achim's Game of Life Page. Retrieved on December 24, 2020.
  13. 13.0 13.1 Achim Flammenkamp (September 18, 2016). "Garden of Eden / Orphan". Achim's Game of Life Page. Retrieved on December 24, 2020.
  14. Achim Flammenkamp (January 27, 2017). "Garden of Eden / Orphan". Achim's Game of Life Page. Retrieved on December 24, 2020.

External links

Forum threads