2

I am just beginning to study cellular automata and I am having trouble understanding the so called Garden of Eden states. How can a deterministic algorithm wind up in a state that has no pre-image, this seems impossible to me?

Ken Taylo
  • 21

2 Answers2

1

Not every state is guaranteed to be possible in cellular automata, so it can never end in a Garden of Eden state.

The Garden of Eden Theorem states that iff an automaton has twins, that is iff it's possible to replace one state with another without changing the future states, then there can be a Garden of Eden state. For sufficiently large sizes of grids the number of potential predecessors (that do not contain a twin pattern) is smaller than the number of future states.

qwr
  • 10,716
1

  • Consider a cellular automaton that turns any state to state $0$ in one step. All states except $0$ are unreachable and therefore so-called Garden of Eden states. Nonetheless this cellular automaton is clearly deterministic. There is no contradiction.

  • But states are local (i.e. the content of a single cell). The Garden of Eden Theorem speaks about patterns of states (i.e. the content of a collection of adjacent cells). Precisely:

    All patterns are reachable if and only if there is no twin patterns (where twin patterns are pairs of patterns that can be exchanged in a given surrounding configuration without changing the image).

For example, in Game of Life, there are twin patterns (a $1$ surrounded by eight $0$s VS. a 3x3 pattern of $0$s) so there must be a Garden of Eden Pattern. I let you find one... :)

user148606
  • 410