The Garden of Eden theorem for cellular automata on group sets

ABSTRACT

We prove the Garden of Eden theorem for big-cellular automata with finite set of states and finite neighbourhood on right amenable left homogeneous spaces with finite stabilisers. It states that the global transition function of such an automaton is surjective if and only if it is pre-injective. Pre-Injectivity means that two global configurations that differ at most on a finite subset and have the same image under the global transition function must be identical. The theorem is proven by showing that the global transition function of an automaton as above is surjective if and only if its image has maximal entropy and that its image has maximal entropy if and only if it is pre-injective. Entropy of a subset of global configurations measures the asymptotic growth rate of the number of finite patterns with growing domains that occur in the subset.

Graphical Abstract

Surjectivity, depicted on the left, is equivalent to pre-infectivity, depicted on the right, for global transition functions of certain cellular automata.

Keywords:

• Cellular automata
• group actions
• homogeneous spaces
• amenability
• entropy
• Garden of Eden theorem

Notes

No potential conflict of interest was reported by the author.