×

The Garden of Eden theorem over generalized cellular automata. (English) Zbl 07896523

Summary: The Garden of Eden theorem is a fundamental result in the theory of cellular automata, which establishes a necessary and sufficient condition for the surjectivity of a cellular automaton with a finite alphabet over an amenable group. Specifically, the theorem states that such an automaton is surjective if and only if it is pre-injective, where pre-injectivity requires that any two almost equal configurations with the same image under the automaton must be equal. This paper focuses on establishing the Garden of Eden theorem over a \(\varphi\)-cellular automaton by demonstrating both Moore theorem and Myhill theorem over \(\varphi\)-cellular automata are true. These results have significant implications for the theoretical framework of the Garden of Eden theorem and its applicability across diverse groups or altered versions of the same group. Overall, this paper provides a more comprehensive study of \(\varphi\)-cellular automata and extends the Garden of Eden theorem to a broader class of automata.

MSC:

37B15 Dynamical aspects of cellular automata
37B10 Symbolic dynamics
68Q80 Cellular automata (computational aspects)
Full Text: DOI

References:

[1] Bartholdi, L., Amenability of groups is characterized by Myhill’s theorem, J. Eur. Math. Soc., 21, 10, 3191-3197, 2019 · Zbl 1458.37017 · doi:10.48550/arXiv.1605.09133
[2] Bartholdi, L., Gardens of Eden and amenability on cellular automata, J. Eur. Math. Soc., 12, 1, 241-248, 2010 · Zbl 1185.37020 · doi:10.4171/JEMS/196
[3] Castillo-Ramirez, A.; Sanchez-Alvarez, M.; Vazquez-Aceves, A.; Zaldivar-Corichi, A., A generalization of cellular automata over groups, Commun. Algebra, 51, 7, 3114-3123, 2023 · Zbl 1518.37019 · doi:10.1080/00927872.2023.2177663
[4] Ceccherini-Silberstein, T.; Coornaert, M., Cellular Automata and Groups. Springer Monographs in Mathematics, 2010, Berlin: Springer, Berlin · Zbl 1218.37004 · doi:10.1007/978-3-642-14034-1
[5] Ceccherini-Silberstein, T.; Machì, A.; Scarabotti, F., Amenable groups and cellular automata, Ann. Inst. Fourier (Grenoble), 49, 2, 673-685, 1999 · Zbl 0920.43001 · doi:10.5802/aif.1686
[6] Lind, D.; Marcus, B., An Introduction to Symbolic Dynamics and Coding, 1995, Cambridge: Cambridge University Press, Cambridge · Zbl 1106.37301 · doi:10.1017/CBO9780511626302
[7] Moore, EF, Machine models of self-reproduction, Proc. Sympos. Appl. Math., 14, 17-34, 1963 · Zbl 0126.32408 · doi:10.1090/psapm/014/9961
[8] Myhill, J., The converse of Moore’s Garden-of-Eden theorem, Proc. Am. Math. Soc., 14, 685-686, 1963 · Zbl 0126.32501
[9] Machì, A.; Mignosi, F., Garden of Eden configurations for cellular automata on Cayley graphs of groups, SIAM J. Discrete Math., 6, 1, 44-56, 1993 · Zbl 0768.68103 · doi:10.1137/0406004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.