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.
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 remainding 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 and third orphan by computer search in 1973. Sadly I have no description of these except they are of rectangle size 6x122, resp. 6x117; his aim was to find Garden of Eden pattern with minimal width. As far as I understand his article, he showed that no of width < 5 exists. All these early found objects were constructed from strips of fixed width which were extended until the new object has no predecessor.

Until end of 20011, 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 2012-03-01 11:22:29   o'clock