Amenable groups and cellular automata (Q1288652): Difference between revisions

The authors study the connection between cellular automata and amenable groups. Using the notions of Garden of Eden (GOE) and mutually erasable (ME) configurations [see \textit{A. Machì} and \textit{F. Mignosi}, SIAM J. Discr. Math. 6, 44-56 (1993; Zbl 0768.68103)], the following main result is proved: For any cellular automaton \((S,{\mathcal G}_A (G),f)\), where \(S\) is the alphabet (set of states), \({\mathcal G}_A(G)\) the Cayley graph of a finitely generated amenable group \(G\) with respect to a finite and symmetric generated system \(A\) and \(f\) the local map, there exist GOE patterns if and only if there exist ME patterns. This extends the theorems of E. F. Moore and J. Myhill to universes which are the Cayley graphs of amenable groups. Some counterexamples of universes are given that show the limits of applicability of the mentioned result.