Garden of Eden (cellular automaton)

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 , this name was coined by John Tukey in the 1950s.

A Garden of Eden is a configuration of the whole lattice (usually one- or two-dimensional infinite square lattice). Each Garden of Eden configuration contains at least one finite pattern with no predecessor. 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.

Searching for the Garden of Eden

It would be possible for a computer program to search for Garden of Eden patterns by systematically examining all possible patterns, in order by increasing size, and by testing all possible predecessors for each pattern to determine whether it is in fact a Garden of Eden. However, the number of patterns that would need to be generated to find a Garden of Eden in this way is exponential in the area of the pattern. This enormous number of patterns would make this approach prohibitively expensive, even for relatively small sizes of patterns.

pioneered a more efficient computational approach for finding orphan patterns, based on the theory of formal languages, that...
Read More