![]() For higher dimensions, determining whether a Garden of Eden exists is an undecidable problem, meaning that there is no algorithm that can be guaranteed to terminate and produce the correct answer. Searching for the Garden of Eden įor one-dimensional cellular automata, Gardens of Eden can be found by an efficient algorithm whose running time is polynomial in the size of the rule table of the automaton. An orphan, then, is a pattern with no predecessor. The definition of predecessors of configurations can be extended to predecessors of patterns:Ī predecessor of a pattern is just a configuration whose successor contains the pattern. ![]() A configuration contains a pattern when the states of the cells in the pattern are the same as the states of the same cells in the configuration (without translating the cells before matching them). Ī pattern, for a given cellular automaton, consists of a finite set of cells together with a state for each of those cells. Ī Garden of Eden is defined to be a configuration with zero predecessors. If the successor of configuration X is configuration Y, then X is a predecessor of Y.Ī configuration may have zero, one, or more predecessors, but it always has exactly one successor. The transition function of the automaton is the function that maps each configuration to its successor. The successor of a configuration is another configuration, formed by applying the update rule simultaneously to every cell. The neighborhood can be an arbitrary finite set of cells, but each two cells should have neighbors in the same relative positions and all cells must use the same update rule.Ī configuration of the automaton is an assignment of a state to every cell. The update rule determines the next state of each cell as a function of its current state and of the current states of certain other nearby cells (the neighborhood of the cell). Often, the grid of cells is the one- or two-dimensional infinite square lattice. The Garden of Eden theorem of Moore and Myhill asserts that a cellular automaton on the square grid, or on a tiling of any higher dimensional Euclidean space, has a Garden of Eden if and only if it has twins, two finite patterns that have the same successors whenever one is substituted for the other.Ī cellular automaton is defined by a grid of cells, a finite set of states that can be assigned to each cell, and an update rule. Nevertheless, computer searches have succeeded in finding these patterns in Conway's Game of Life. However, for any Garden of Eden there is a finite pattern (a subset of cells and their states, called an orphan) with the same property of having no predecessor, no matter how the remaining cells are filled in.Ī configuration of the whole automaton is a Garden of Eden if and only if it contains an orphan.įor one-dimensional cellular automata, orphans and Gardens of Eden can be found by an efficient algorithm, but for higher dimensions this is an undecidable problem. ![]() Ī Garden of Eden is determined by the state of every cell in the automaton (usually a one- or two-dimensional infinite square lattice of cells). John Tukey named these configurations after the Garden of Eden in Abrahamic religions, which was created out of nowhere. It can be the initial configuration of the automaton but cannot arise in any other way. In a cellular automaton, a Garden of Eden is a configuration that has no predecessor. Black squares are required live cells blue x's are required dead cells. ![]() An orphan in Life found by Achim Flammenkamp.
0 Comments
Leave a Reply. |