Garden of Eden theorem

Remarks

A configuration outside the image of $F$ is called a Garden of Eden: it has no predecessor. So the theorem says that a Garden of Eden exists exactly when two configurations that differ at finitely many sites have the same image. The proof compares counts: in a large box of side $n$, the number of patterns grows like $\abs{A}^{n^d}$, while the boundary of the box has only about $n^{d-1}$ sites. A missing pattern, or a pair of patterns with the same image, changes the exponential count by a factor that the boundary cannot compensate. The theorem is due to Moore and Myhill. Example: rule 90 in one dimension is surjective, so it is pre-injective. It is not injective, since the all-$0$ and the all-$1$ configurations both map to the all-$0$ configuration, but these are not asymptotic. Conway's Game of Life is not surjective: it has Garden of Eden configurations. The theorem extends to cellular automata on amenable groups, and it fails for the free group on two generators.

Going deeper

For a student

Injective implies pre-injective, so every injective cellular automaton on $\Z^d$ is surjective. This is a dynamical analogue of the fact that an injective map of a finite set to itself is onto. The theorem is often used to show that a rule has Garden of Eden patterns by exhibiting two mutually erasable patterns. Its extension to amenable groups by Ceccherini-Silberstein, Machì and Scarabotti links it to amenable group actions. For the free group of rank two there are surjective cellular automata that are not pre-injective.