Difference between revisions of "Garden of Eden"
m (→Records) |
m (→Records: Note on box-height/width) |
||
(17 intermediate revisions by 4 users not shown) | |||
Line 1: | Line 1: | ||
{{Glossary}} | {{Glossary}} | ||
A '''Garden of Eden''' is a [[pattern]] that has no [[parent]]s and thus can only occur in [[generation]] 0. The term was first used in connection with [[cellular automaton|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 [[#Garden of Eden theorem|theorem]] by Edward Moore that guarantees their existence in a wide class of cellular automata. | A '''Garden of Eden''' is a [[pattern]] that has no [[parent]]s and thus can only occur in [[generation]] 0. The term was first used in connection with [[cellular automaton|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 [[#Garden of Eden theorem|theorem]] by Edward Moore that guarantees their existence in a wide class of cellular automata. | ||
Line 22: | Line 21: | ||
==Explicit examples== | ==Explicit examples== | ||
Several Gardens of Eden and orphans have been constructed, [[Garden of Eden 1|the first]] by [[:Category:Patterns found by Roger Banks|Roger Banks]] et al. at MIT in [[:Category:Patterns found in 1971|1971]]. It had a [[bounding box]] of size 33 × 9 and had 226 [[cell]]s. 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. | Several Gardens of Eden and orphans have been constructed, [[Garden of Eden 1|the first]] by [[:Category:Patterns found by Roger Banks|Roger Banks]] et al. at MIT in [[:Category:Patterns found in 1971|1971]]. It had a [[bounding box]] of size 33 × 9 and had 226 [[cell]]s. 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 [[:Category:Patterns found in 2016|2016]], Steven Eker found a Garden of Eden fitting inside a 5 x 83 bounding box.<ref>{{cite web|url=http://wwwhomes.uni-bielefeld.de/achim/orphan.html |title=Garden of Eden / Orphan |author=Achim Flammenkamp |date=April 14, 2016 |accessdate=April 30, 2016}}</ref> 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 [[:Category:Patterns found in 1991|1991]], contained 143 cells, and had a bounding box of size 14 × 14. [[Garden of Eden 3]] was found by Achim Flammenkamp in [[:Category:Patterns found in 2004|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]],<ref>{{cite web|url=http://wwwhomes.uni-bielefeld.de/achim/orphan_2nd.html |title=Garden of Eden / Orphan |author=Achim Flammenkamp |date=November 7, 2008 |accessdate=February 14, 2009}}</ref> 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, [[:Category:Patterns found in 2011|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]].<ref>{{cite web|url=http://pentadecathlon.com/lifeNews/2012/01/gardens_of_eden.html|title=Gardens of Eden|author=[[Adam P. Goucher]]|date=January 14, 2012|accessdate=June 18, 2012}}</ref> | |||
[[Image:GardensofEden.png|framed|center|Many Gardens of Eden found by Nicolay Beluchenko in 2009<br />{{JavaRLE|gardensofeden}}]] | [[Image:GardensofEden.png|framed|center|Many Gardens of Eden found by Nicolay Beluchenko in 2009<br />{{JavaRLE|gardensofeden}}]] | ||
==Records== | ==Records== | ||
List of records and notable patterns, '''<font color="red">red</font>''' are records | List of records and notable patterns, '''<font color="red">red</font>''' are records. Box-height is assumed to be less than or equal to box-width. | ||
{| class="wikitable sortable" | {| class="wikitable sortable" | ||
Line 35: | Line 36: | ||
! Year | ! Year | ||
! Author | ! Author | ||
! Box- | ! Box-height | ||
! Box- | ! Box-width | ||
! Box | ! Box-cells | ||
! Orphan | ! Orphan | ||
! On-Cells | ! On-Cells | ||
Line 51: | Line 52: | ||
| 297 | | 297 | ||
| 226 | | 226 | ||
| | | 0.7609 | ||
| - | | - | ||
| [[Garden_of_Eden_1|GoE#1]] | | [[Garden_of_Eden_1|GoE#1]] | ||
Line 57: | Line 58: | ||
| 1973 | | 1973 | ||
| [[Jean Hardouin-Duparc]] | | [[Jean Hardouin-Duparc]] | ||
| | | 6 | ||
| 122 | | 122 | ||
| 732 | | 732 | ||
| | | 732 | ||
| | | 576 | ||
| | | 0.7869 | ||
| - | | - | ||
| [http://wwwhomes.uni-bielefeld.de/achim/orphan.html] | | [http://wwwhomes.uni-bielefeld.de/achim/orphan.html] | ||
|- | |- | ||
| 1973 | | 1973 | ||
| | | Jean Hardouin-Duparc | ||
| 6 | | 6 | ||
| 117 | | 117 | ||
Line 84: | Line 85: | ||
| 196 | | 196 | ||
| 143 | | 143 | ||
| 0 | | 0.7296 | ||
| - | | - | ||
| [[Garden_of_Eden_2|GoE#2]] | | [[Garden_of_Eden_2|GoE#2]] | ||
|- | |- | ||
| 2004 | | 2004 | ||
| | | Achim Flammenkamp | ||
| 12 | | 12 | ||
| 13 | | 13 | ||
Line 95: | Line 96: | ||
| 136 | | 136 | ||
| 81 | | 81 | ||
| 0 | | 0.5956 | ||
| - | | - | ||
| [[Garden_of_Eden_3|GoE#3]] | | [[Garden_of_Eden_3|GoE#3]] | ||
|- | |- | ||
| 2004 | | 2004 | ||
| | | Achim Flammenkamp | ||
| 11 | | 11 | ||
| 12 | | 12 | ||
Line 106: | Line 107: | ||
| 113 | | 113 | ||
| 72 | | 72 | ||
| 0 | | 0.6372 | ||
| - | | - | ||
| [[Garden_of_Eden_4|GoE#4]] | | [[Garden_of_Eden_4|GoE#4]] | ||
|- | |- | ||
| 2004 | | 2004 | ||
| | | Achim Flammenkamp | ||
| 10 | | 10 | ||
| 13 | | 13 | ||
Line 128: | Line 129: | ||
| 109 | | 109 | ||
| 69 | | 69 | ||
| 0 | | 0.6330 | ||
| C4 | | C4 | ||
| [[Flower_of_Eden|GoE#5]] | | [[Flower_of_Eden|GoE#5]] | ||
|- | |- | ||
| 2009 | | 2009 | ||
| | | Nicolay Beluchenko | ||
| 11 | | 11 | ||
| 11 | | 11 | ||
Line 139: | Line 140: | ||
| 113 | | 113 | ||
| 59 | | 59 | ||
| 0 | | 0.5221 | ||
| - | | - | ||
| [http://wwwhomes.uni-bielefeld.de/achim/orphan_3rd.html] | | [http://wwwhomes.uni-bielefeld.de/achim/orphan_3rd.html] | ||
|- | |- | ||
| 2009 | | 2009 | ||
| | | Nicolay Beluchenko | ||
| 11 | | 11 | ||
| 11 | | 11 | ||
Line 150: | Line 151: | ||
| 110 | | 110 | ||
| 49 | | 49 | ||
| 0 | | 0.4455 | ||
| D2_x | | D2_x | ||
| [http://wwwhomes.uni-bielefeld.de/achim/orphan_4th.html] | | [http://wwwhomes.uni-bielefeld.de/achim/orphan_4th.html] | ||
|- | |- | ||
| 2009 | | 2009 | ||
| | | Nicolay Beluchenko | ||
| 11 | | 11 | ||
| 13 | | 13 | ||
Line 161: | Line 162: | ||
| 139 | | 139 | ||
| 58 | | 58 | ||
| 0 | | 0.4173 | ||
| - | | - | ||
| [http://wwwhomes.uni-bielefeld.de/achim/orphan_4th.html] | | [http://wwwhomes.uni-bielefeld.de/achim/orphan_4th.html] | ||
|- | |- | ||
| 2009 | | 2009 | ||
| | | Nicolay Beluchenko | ||
| 11 | | 11 | ||
| 11 | | 11 | ||
Line 172: | Line 173: | ||
| 115 | | 115 | ||
| 47 | | 47 | ||
| 0 | | 0.4087 | ||
| D2_x | | D2_x | ||
| [http://wwwhomes.uni-bielefeld.de/achim/orphan_5th.html] | | [http://wwwhomes.uni-bielefeld.de/achim/orphan_5th.html] | ||
|- | |- | ||
| 2009 | | 2009 | ||
| | | Nicolay Beluchenko | ||
| 11 | | 11 | ||
| 11 | | 11 | ||
Line 183: | Line 184: | ||
| 107 | | 107 | ||
| 51 | | 51 | ||
| 0 | | 0.4766 | ||
| | | D4_x | ||
| [http://wwwhomes.uni-bielefeld.de/achim/orphan_5th.html] | | [http://wwwhomes.uni-bielefeld.de/achim/orphan_5th.html] | ||
|- | |- | ||
| 2009 | | 2009 | ||
| | | Nicolay Beluchenko | ||
| 11 | | 11 | ||
| 11 | | 11 | ||
Line 194: | Line 195: | ||
| 113 | | 113 | ||
| style="color: red;" | '''45''' | | style="color: red;" | '''45''' | ||
| 0 | | 0.3982 | ||
| D4_x | | D4_x | ||
| [http://wwwhomes.uni-bielefeld.de/achim/orphan_6th.html] | | [http://wwwhomes.uni-bielefeld.de/achim/orphan_6th.html] | ||
|- | |- | ||
| 2009 | | 2009 | ||
| | | Nicolay Beluchenko | ||
| 12 | | 12 | ||
| 12 | | 12 | ||
Line 205: | Line 206: | ||
| 129 | | 129 | ||
| 50 | | 50 | ||
| 0 | | 0.3876 | ||
| - | | - | ||
| [http://wwwhomes.uni-bielefeld.de/achim/orphan_6th.html] | | [http://wwwhomes.uni-bielefeld.de/achim/orphan_6th.html] | ||
Line 214: | Line 215: | ||
| 11 | | 11 | ||
| 121 | | 121 | ||
| | | 93 | ||
| 65 | | 65 | ||
| 0 | | 0.6989 | ||
| D8 | | D8 | ||
| almost [[Garden_of_Eden_6|GoE#6]] | | almost [[Garden_of_Eden_6|GoE#6]] | ||
|- | |- | ||
| 2011 | | 2011 | ||
| | | Marijn Heule et al. | ||
| 11 | | 11 | ||
| 11 | | 11 | ||
| 121 | | 121 | ||
| 119 | | 119 | ||
| style="color: | | style="color: red;" | '''45''' | ||
| 0 | | 0.3781 | ||
| D8 | | D8 | ||
| almost [[Garden_of_Eden_6|GoE#6]] | | almost [[Garden_of_Eden_6|GoE#6]] | ||
|- | |- | ||
| 2011 | | 2011 | ||
| | | Marijn Heule et al. | ||
| 13 | | 13 | ||
| 13 | | 13 | ||
Line 249: | Line 239: | ||
| 153 | | 153 | ||
| 49 | | 49 | ||
| style="color: red;" | '''0 | | style="color: red;" | '''0.3203''' | ||
| D8 | | D8 | ||
| [http://wwwhomes.uni-bielefeld.de/achim/orphan_8th.html] | | [http://wwwhomes.uni-bielefeld.de/achim/orphan_8th.html] | ||
|- | |||
| 2011 | |||
| Marijn Heule et al. | |||
| 10 | |||
| style="color: red;" | '''10''' | |||
| 100 | |||
| 92 | |||
| 56 | |||
| 0.6087 | |||
| C4 | |||
| [[Garden_of_Eden_6|GoE#6]] | |||
|- | |- | ||
| 2015 | | 2015 | ||
Line 260: | Line 261: | ||
| 99 | | 99 | ||
| 66 | | 66 | ||
| 0 | | 0.6667 | ||
| - | | - | ||
| [http://wwwhomes.uni-bielefeld.de/achim/orphan_9th.html] | | [http://wwwhomes.uni-bielefeld.de/achim/orphan_9th.html] | ||
|- | |- | ||
| 2016 | | 2016 | ||
| | | Steven Eker | ||
| 8 | | 8 | ||
| 12 | | 12 | ||
Line 271: | Line 272: | ||
| 96 | | 96 | ||
| 57 | | 57 | ||
| 0 | | 0.5938 | ||
| - | | - | ||
| [http://wwwhomes.uni-bielefeld.de/achim/orphan_9th.html] | | [http://wwwhomes.uni-bielefeld.de/achim/orphan_9th.html] | ||
|- | |||
| 2016 | |||
| Steven Eker | |||
| style="color: red;" | '''5''' | |||
| 83 | |||
| 415 | |||
| 410 | |||
| 284 | |||
| 0.6927 | |||
| - | |||
| [http://wwwhomes.uni-bielefeld.de/achim/orphan.html] | |||
|- | |||
| 2016 | |||
| Steven Eker | |||
| style="color: red;" | '''5''' | |||
| 45 | |||
| 225 | |||
| 223 | |||
| 139 | |||
| 0.6233 | |||
| D2_+1 | |||
| [http://wwwhomes.uni-bielefeld.de/achim/orphan_10th.html] | |||
|- | |||
| 2016 | |||
| Steven Eker | |||
| 9 | |||
| 11 | |||
| 99 | |||
| 89 | |||
| 55 | |||
| 0.6180 | |||
| - | |||
| [http://wwwhomes.uni-bielefeld.de/achim/orphan_10th.html] | |||
|- | |||
| 2017 | |||
| Steven Eker | |||
| 9 | |||
| 11 | |||
| 99 | |||
| style="color: red;" | '''88''' | |||
| 50 | |||
| 0.5682 | |||
| - | |||
| [http://wwwhomes.uni-bielefeld.de/achim/orphan_11th.html] | |||
|} | |} | ||
==See also== | ==See also== | ||
*[[:Category:Gardens of Eden|List of Gardens of Eden]] | *[[:Category:Gardens of Eden|List of Gardens of Eden]] | ||
*[[Grandfather problem]] | |||
==References== | ==References== | ||
Line 284: | Line 330: | ||
==External links== | ==External links== | ||
{{LinkLexicon|lex_g.htm#gardenofeden}} | {{LinkLexicon|lex_g.htm#gardenofeden}} | ||
{{LinkWikipedia|Garden_of_Eden_(cellular_automaton)|name=Garden of Eden (cellular automaton)}} | |||
===Forum threads=== | |||
{{LinkForumThread|f=7|t=1361|title=Finding Gardens of Eden}} | |||
{{LinkForumThread|f=7|t=1035|title=Conway's Life: Garden of Eden Pattern}} |
Revision as of 10:05, 20 August 2017
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 bits. 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.
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 x 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]
Records
List of records and notable patterns, red are records. Box-height is assumed to be less than or equal to box-width.
Year | Author | Box-height | Box-width | Box-cells | Orphan | On-Cells | Density | Symmetry | Note |
---|---|---|---|---|---|---|---|---|---|
1971 | Roger Banks et al. | 9 | 33 | 297 | 297 | 226 | 0.7609 | - | GoE#1 |
1973 | Jean Hardouin-Duparc | 6 | 122 | 732 | 732 | 576 | 0.7869 | - | [1] |
1973 | Jean Hardouin-Duparc | 6 | 117 | 702 | ? | ? | - | [2] | |
1991 | Achim Flammenkamp | 14 | 14 | 196 | 196 | 143 | 0.7296 | - | GoE#2 |
2004 | Achim Flammenkamp | 12 | 13 | 156 | 136 | 81 | 0.5956 | - | GoE#3 |
2004 | Achim Flammenkamp | 11 | 12 | 132 | 113 | 72 | 0.6372 | - | GoE#4 |
2004 | Achim Flammenkamp | 10 | 13 | 130 | ? | ? | - | [3] not a GoE, one parent | |
2009 | Nicolay Beluchenko | 11 | 11 | 121 | 109 | 69 | 0.6330 | C4 | GoE#5 |
2009 | Nicolay Beluchenko | 11 | 11 | 121 | 113 | 59 | 0.5221 | - | [4] |
2009 | Nicolay Beluchenko | 11 | 11 | 121 | 110 | 49 | 0.4455 | D2_x | [5] |
2009 | Nicolay Beluchenko | 11 | 13 | 143 | 139 | 58 | 0.4173 | - | [6] |
2009 | Nicolay Beluchenko | 11 | 11 | 121 | 115 | 47 | 0.4087 | D2_x | [7] |
2009 | Nicolay Beluchenko | 11 | 11 | 121 | 107 | 51 | 0.4766 | D4_x | [8] |
2009 | Nicolay Beluchenko | 11 | 11 | 121 | 113 | 45 | 0.3982 | D4_x | [9] |
2009 | Nicolay Beluchenko | 12 | 12 | 144 | 129 | 50 | 0.3876 | - | [10] |
2011 | Marijn Heule et al. | 11 | 11 | 121 | 93 | 65 | 0.6989 | D8 | almost GoE#6 |
2011 | Marijn Heule et al. | 11 | 11 | 121 | 119 | 45 | 0.3781 | D8 | almost GoE#6 |
2011 | Marijn Heule et al. | 13 | 13 | 169 | 153 | 49 | 0.3203 | D8 | [11] |
2011 | Marijn Heule et al. | 10 | 10 | 100 | 92 | 56 | 0.6087 | C4 | GoE#6 |
2015 | Steven Eker | 9 | 11 | 99 | 99 | 66 | 0.6667 | - | [12] |
2016 | Steven Eker | 8 | 12 | 96 | 96 | 57 | 0.5938 | - | [13] |
2016 | Steven Eker | 5 | 83 | 415 | 410 | 284 | 0.6927 | - | [14] |
2016 | Steven Eker | 5 | 45 | 225 | 223 | 139 | 0.6233 | D2_+1 | [15] |
2016 | Steven Eker | 9 | 11 | 99 | 89 | 55 | 0.6180 | - | [16] |
2017 | Steven Eker | 9 | 11 | 99 | 88 | 50 | 0.5682 | - | [17] |
See also
References
- ↑ Achim Flammenkamp (April 14, 2016). "Garden of Eden / Orphan". Retrieved on April 30, 2016.
- ↑ Achim Flammenkamp (November 7, 2008). "Garden of Eden / Orphan". Retrieved on February 14, 2009.
- ↑ Adam P. Goucher (January 14, 2012). "Gardens of Eden". Retrieved on June 18, 2012.
External links
- Garden of Eden at the Life Lexicon
- Garden of Eden (cellular automaton) at Wikipedia
Forum threads
- Finding Gardens of Eden (discussion thread) at the ConwayLife.com forums
- Conway's Life: Garden of Eden Pattern (discussion thread) at the ConwayLife.com forums