Garden of Eden / Orphan

Firstly a notation coined by J.H.Conway: an 'orphan' is a finite configuration or pattern which can not arise by evolution of a given automaton rule. It may be expanded by adding arbitrary cell states and still can only appear as starting configuration in a cellular automaton. A 'garden of Eden' is a finite configuration embedded in the ground-state of the automaton / empty universe and also can not be generated by the specific (GoL-)rules.
This Garden of Eden was discovered in January 1991 in the 2-state cellular automaton known as Game of Life.
Thus the previous mentioned 143-bit Garden of Eden pattern living in a 14x14 box is also a 196 sized orphan. Moreover, since 1991 it is easy to construct further GoL-orphans inside 15x15 rectangles. Now let us restrict to the Game of Life rules again.

On 14th June 2004, the more than 13 years old record was remarkably improved: This Orphan , needing only 136 cells, became the new record-holder for smallest size. And its corresponding 81-bit Garden of Eden, , fits in a 13x12 rectangle.
As usual the challenge remains: Can you find a smaller one --- i.e. proving that your example has no predecessor in Game of Life and has fewer living cells or needs a smaller area for residence? YES

Historical notes: The first published Garden of Eden pattern in Game of Life , 1971 constructed by Roger Banks, Mike Beeler, Rich Schroeppel et al. at MIT and consisting of 226 bits, is a 33x9 sized orphan. On June 16th 2004, it was noticed that if the rightmost 5 columns (high lightened in the picture) are cut off, then the remaining 193-bit object is an orphan as well as an Garden of Eden, too! Thus the question arises: why did Roger Banks published the artifically enlarged orphan (I imputed he knew this fact)?
At the Universite de Bordeaux I, Jean Hardouin-Duparc found a second 6x122 and third 6x117 Garden of Eden by computer search in 1973.
Surprisingly in October 2016, Mats Ahlbeck, from Stockholm, Sweden, noticed that the published 6x122 pattern of Jean Hardouin-Duparc is neither a Garden of Eden nor an orphan by constructing a predecessor. Shortly afterwards Steven Eker checked whether there is a single error in the print of the image in the french publication. But it was not. So the probability is high that Jean Hardouin-Duparc make an error during his computer verification of this pattern.

Thanks to Steven Eker who send me a photocopy of the larger one I can present this want-to-be Garden of Eden pattern now which consists of 576 on-cells; Jean's aim was to find Garden of Eden pattern with minimal width. In 2016 Steven Eker pointed out, that Jean Hardouin-Duparc only proved that height 1 is impossible and unsuccessfully searched for Garden of Eden pattern up to height 5. All these early found objects were constructed from strips of fixed width which were extended until the new object has no predecessor. In April 2016 Steven Eker, working at SRI International, California, USA, communicated me in a private email that he has extended Jean's automaton/grammar based proof and was able to prove with more sophisticated techniques the non-existence of Garden of Eden pattern of height 2 and height 3. With up-to-date hardware he was still unable to decide the case of height 4 due to the enormous state space of this tree-search. But at height 5, contrary to popular belief, Steven Eker found this orphan! Also he was able to find smaller ones of height 6 and height 7 than previously known.

By the end of 2011, Marijn Heule, Christiaan Hartman, Kees Kwekkeboom and Alain Noels from the TU Delft had established by extensive computations the fact, that all Game of Life patterns bounded by a 6x6 rectangle have a predecessor.

Achim Flammenkamp
Last update: Bielefeld, den 2017-01-27 19:17:15   o'clock