Garden of Eden theorem

In a cellular automaton, a Garden of Eden is a configuration that has no predecessor. It can be the initial configuration of the automaton but cannot appear later in the evolution of the automaton. John Tukey named these configuration after the Garden of Eden in Abrahamic religions, which was created out of nowhere.

A 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). 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. A configuration of the whole automaton is a Garden of Eden if and only if it contains an orphan. For 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. Nevertheless, computer searches have succeeded in finding these patterns in Conway's Game of Life.

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.

A 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. Often, the grid of cells is the one- or two-dimensional infinite square lattice. 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). 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. A configuration of the automaton is an assignment of a state to every cell.

...
Wikipedia