Searching For The Garden of Eden
It would be possible for a computer program to search for orphan 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 an orphan. 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 type of brute-force search prohibitively expensive, even for relatively small sizes of patterns.
Jean Hardouin-Duparc (1972/73, 1974) pioneered a more efficient computational approach for finding orphan patterns, based on the theory of formal languages, that is exponential in the width of the pattern rather than its area. The key idea is that, for any fixed width, it is relatively straightforward to construct a nondeterministic finite automaton that recognizes patterns of a given width that have a predecessor. The input symbols to this machine describe each row of the pattern, and the states of the machine describe the nearby rows of possible predecessors for the part of the pattern that has been input so far. One can construct from this machine another finite state machine that recognizes the complementary set, the patterns that do not have predecessors, by converting the nondeterministic finite state machine to a deterministic finite automaton and then complementing its set of accepting states. Once a machine recognizing the complementary set has been constructed, one may test whether the language it recognizes is empty, by searching for a path from the start state to an accepting state. This path, if it exists, gives a row-by-row description of an orphan pattern.
The first known Garden of Eden pattern in Conway's Game of Life, fitting in a 9 × 33 rectangle, was identified as a candidate to be a Garden of Eden by Roger Banks in 1971, and then verified by an exhaustive backtracking search for predecessors. Subsequently, Hardouin-Duparc used his formal language approach to find the narrowest possible Gardens of Eden in Conway's Game of Life, only six cells wide. The smallest known orphan pattern in Conway's Game of Life was found by Marijn Heule, Christiaan Hartman, Kees Kwekkeboom and Alain Noels in December 2011. It has 56 living cells and fits in an 10x10 square.
Read more about this topic: Garden Of Eden (cellular Automaton)
Famous quotes containing the words garden of eden, searching for, searching, garden and/or eden:
“It gets to seem as if way back in the Garden of Eden after the Fall, Adam and Eve had begged the Lord to forgive them and He, in his boundless exasperation, had said, “All right, then. Stay. Stay in the Garden. Get civilized. Procreate. Muck it up.” And they did.”
—Diane Arbus (1923–1971)
““Why were you searching for me? Did you not know that I must be in my Father’s house?””
—Bible: New Testament, Luke 2:49.
Jesus to his parents when they found him in the temple.
““Why were you searching for me? Did you not know that I must be in my Father’s house?””
—Bible: New Testament, Luke 2:49.
Jesus to his parents when they found him in the temple.
“Two wooden tubs of blue hydrangeas stand at the foot of the stone steps.
The sky is a blue gum streaked with rose. The trees are black.
The grackles crack their throats of bone in the smooth air.
Moisture and heat have swollen the garden into a slum of bloom.
Pardie! Summer is like a fat beast, sleepy in mildew....”
—Wallace Stevens (1879–1955)
“We best avoid wars by taking even physical action to stop small ones.”
—Anthony, Sir Eden (1897–1977)