User:JonRichfield/Garden of Eden (cellular automaton)

A Garden of Eden in a given type of cellular automaton is any configuration that cannot occur in any generation after the first. It follows that the creation of a Garden of Eden can never follow the rules of that automaton, but requires an outside agent before the first generation. John Tukey accordingly coined the term in analogy to the Garden of Eden described in Abrahamic religions; that biblical garden too had to be specially created, because it could not have arisen spontaneously from anything that had existed earlier in creation.

Definitions

Main article: Cellular automaton

• A cellular automaton exists in a space commonly called a grid. As a rule the grid is a lattice that defines a regular tiling of a space by a primitive cell. The space may or may not be notionally finite, and may have any well-defined topology, but it is N-dimensional, where most familiarly, N=1 or N=2.
• A cell in an automaton contains one lattice point in any defined state. For example a cell may be unoccupied ("empty") or occupied by a defined abstract value. Commonly a 2-dimensional cellular automaton is defined as occupying a square lattice of primitive cells, as in Conway's Game of Life, in which each cell is simply "empty" ("dead") or "full" ("alive").
• The configuration of a cellular automaton is the full representation of the state of every cell in the automaton's space.
• A pattern within a configuration is a finite arrangement of cells, not necessarily a proper subset, together with a particular state for each cell.
• For a given pattern occurs in a given configuration implies that some part of the configuration contains a region of the same number of active cells with the same mutual coordinates. In most contexts the pattern must be delimited from the rest of the automaton, for instance by a sufficiently wide border of quiescent neighbouring cells to permit the pattern to behave independently of the rest of the configuration during some relevant sequence of generations.
• Each configuration in turn may be called the current generation of the automaton; it becomes the predecessor of the following (successor) generation. In operation, an automaton applies a transition function to the cells of each generation. The transition function derives a successor state for each cell in the configuration, thereby producing the successor generation. The configurations of successor generations commonly differ from predecessors.
• A cell is said to be quiescent if its state remains stable until its neighbouring cells force a change, while it in turn cannot affect the state of any neighbouring cells. The exact meaning of quiescence varies with the nature of the automaton's transition function, but in Life for instance, empty cells may be regarded as quiescent.
• An oscillator is a pattern that is not quiescent, but in which the same pattern repeats periodically. For instance in the game of Life, three cells in a horizontal row change to a vertical row in the successor generation, then back again. This is an example of an oscillator of period two in a square 5X5 region.
• An orphan in a given type of automaton is any pattern that cannot be the successor of any predecessor pattern. Consider a special class of orphan: for convenience call it a skeletal orphan, one in which rendering any cells quiescent before applying the transition function, would produce a non-orphan.

Elementary implications of the concept

The nature of the concept of the Garden of Eden has several implications.

• No orphan can be either quiescent, an oscillator, or otherwise stable; it must differ from all its successors or it would be its own ancestor. It is possible in at least some classes of cellular automata, for some pattern to be its own predecessor, or to be an oscillator, but such that no pattern other than a phase in its own period can generate it. Though such patterns are of interest in their own right, they are by definition not orphans.
• Any configuration is a Garden of Eden if and only if it contains an orphan, skeletal or not,.
• Any configuration that contains at least one orphan remains a Garden of Eden no matter how many mutually independent orphans it contains.
• A configuration that contains any occupied cells apart from a single skeletal orphan is not itself skeletal, even if it contains nothing but multiple orphans that in isolation would be skeletal.
• Any Garden of Eden can be reduced to a skeletal orphan by removal of as many non-quiescent cells as necessary.