Theorem 1 (Moore, 1962)
Let be a cellular automaton on with finitely many states. If has two mutually erasable patterns, then it has an orphan pattern.
In other words, surjective -dimensional cellular automata are pre-injective.
The same year, John Myhill proved the converse implication.
Theorem 2 (Myhill, 1962)
Let be a cellular automaton on with finitely many states. If has an orphan pattern, then it has two mutually erasable patterns.
In other words, pre-injective -dimensional cellular automata are surjective.
An injective -dimensional cellular automaton is surjective.
Let , , , . For every sufficiently large ,
Observe that, if and
then is the number of possible hypercubic patterns of side , while is the maximum number of their images via .
which is true for large enough since while
Proof of Moore’s theorem. Suppose has two mutually erasable patterns , : it is not restrictive to suppose that their common support is a -hypercube of side . Define an equivalence relation on patterns of side by stating that if and only if : since and are mutually erasable, has at most equivalence classes.
By the same criterion, we define a family of equivalence relations between hypercubic patterns of side . Each such pattern can be subdivided into subpatterns of side : and it is clear that, if two patterns are in relation , then each of those subpatterns is in relation .
Proof of Myhill’s theorem. Let be an orphan pattern for . Again, it is not restrictive to suppose that the support of is a hypercube of side . For let be the number of patterns of side that are not orphan. Split each pattern of side into patterns of side , as we did before. Then cannot exceed the number of those that do not contain a copy of , which in turn is at most .
Take so large that (1) is satisfied: for a fixed state , and for , there are more configurations that take value outside the hypercube than there are configurations that take value outside the hypercube and are not Gardens of Eden. As the configurations of the second type are the images of those the first type, there must be two with the same image: those configurations correspond to two mutually erasable patterns.
Theorems 1 and 2 have been shown  to hold for cellular automata on amenable groups. Moore’s theorem, in fact, characterizes amenable groups (cf. ): whether Myhill’s theorem also does, is an open problem.
- 1 Bartholdi, L. (2010) Gardens of Eden and amenability on cellular automata. J. Eur. Math. Soc. 12(1), 141–148. Preprint: arXiv:0709.4280v1
- 2 Ceccherini-Silberstein, T., Machì, A. and Scarabotti, F. (1999) Amenable groups and cellular automata. Annales de l’Institut Fourier, Grenoble 49(2), 673–685.
- 3 Moore, E.F. (1962) Machine models of self-reproduction. Proc. Symp. Appl. Math. 14, 17–33.
- 4 Myhill, J. (1962) The converse of Moore’s Garden-of-Eden theorem. Proc. Amer. Mat. Soc. 14, 685–686.
|Date of creation||2013-03-22 19:22:07|
|Last modified on||2013-03-22 19:22:07|
|Last modified by||Ziosilvio (18733)|