betaFeedback

WorksComputer Science

Topological Entropy of Group Cellular Automata is Effectively Computable

Abstract

Topological entropy is a fundamental invariant of dynamical systems, quantifying their complexity. For cellular automata, however, determining topological entropy is generally algorithmically intractable. We study group cellular automata, namely cellular automata over a finite group alphabet whose global map is a group endomorphism. In dimension one, we decompose topological entropy into two one-sided components describing information propagating from the left and from the right in space–time. We introduce finite families of left and right traces and prove that the entropy is the sum of their growth rates. Hence, the entropy is completely determined by the growth rate of a fixed-width family of space–time patterns. This reduction from arbitrarily large windows to uniformly bounded width yields an effective procedure for computing the entropy. In particular, the entropy of every one-dimensional group cellular automaton is the logarithm of a positive integer. Using Pontryagin duality and the Bridge Theorem between topological and algebraic entropy, we also derive an explicit formula for linear cellular automata over (Z/pZ)n(\mathbb{Z}/p\mathbb{Z})^n in terms of their characteristic polynomial. Moreover, in every dimension D≥2D\geq 2, a group cellular automaton is either equicontinuous with zero entropy or sensitive to initial conditions with infinite entropy. Combined with decidability of equicontinuity, this implies that topological entropy is effectively computable from the local rule in every dimension. Thus, group cellular automata form a natural nontrivial class in which algebraic structure restores computability of topological entropy.

Introduction

Cellular automata (CAs) are discrete-time dynamical systems defined by the synchronous iteration of a local rule on an infinite lattice. They were originally introduced by von Neumann as abstract models of self-reproducing systems [40], and later studied systematically within symbolic dynamics and theoretical computer science. A cellular automaton consists of a regular grid of variables, typically indexed by ZD\mathbb{Z}^{D}, each taking values in a finite alphabet, and evolving in discrete time according to a rule that updates every variable based only on the states of a finite neighborhood (for an introduction to CA theory, see, e.g., [9, 22, 23]).

Despite the simplicity of their local definition, cellular automata are capable of generating a wide range of dynamical behaviors, from highly regular dynamics to complex and chaotic evolutions (see, e.g., [43]).

CAs have been the subject of significant research and are applied in various fields, including computer science, physics, mathematics, biology, and chemistry, for purposes such as simulating natural phenomena, generating pseudo-random numbers, processing images, analyzing universal computation models, and cryptography (see for example [3, 11, 12, 27, 35]).

From a mathematical perspective, the Curtis-Hedlund-Lyndon theorem provides a complete characterization of cellular automata as exactly the continuous maps on the full shift that commute with the shift action [23].

A central goal in the theory of cellular automata is to quantify dynamical complexity. Among the most important invariants, topological entropy measures the asymptotic rate at which distinguishable orbit segments proliferate, and it is widely used as an indicator of chaotic behavior in symbolic dynamics and cellular systems (see for example [6, 26, 32, 38]). For cellular automata, entropy admits a concrete combinatorial interpretation: it can be expressed through the growth rate of the number of distinct space-time patterns occurring in the evolution of the automaton [26] (see Proposition 3 for arbitrary dimension). This viewpoint makes entropy particularly natural for CAs, as it directly quantifies the production of new patterns in space-time.

The problem of computing topological entropy for cellular automata has been extensively studied and is known to exhibit strong algorithmic limitations. In a seminal paper, Hurd, Kari, and Culik proved that the topological entropy of one-dimensional cellular automata is not computable, showing in particular that there is no algorithm deciding whether the entropy is zero [26]. This result established topological entropy as an intrinsically intractable invariant for general cellular automata and initiated a line of research on its computational complexity.

Subsequent work further clarified the scope of these negative results. Guillon and Zinoviadis showed that the entropies of one-dimensional cellular automata are exactly the right-computable real numbers, while in dimension two the class of achievable entropies becomes strictly larger, encompassing Σ2\Sigma_2 real numbers and infinity [21]. These results provide a precise computability-theoretic classification of cellular automaton entropies, highlighting a sharp distinction between dimensions. More recently, it has been shown that undecidability persists even under strong dynamical constraints, such as reversibility, as the problem of deciding whether a reversible one-dimensional cellular automaton has zero entropy remains undecidable [24].

On the positive side, computability of entropy has been established for several restricted but structurally meaningful classes of cellular automata. D’Amico, Manzini, and Margara proved that the entropy is computable for linear cellular automata over Z/mZ\mathbb{Z}/m\mathbb{Z} and for positively expansive cellular automata [10]. These results indicate that additional algebraic or dynamical rigidity can restore algorithmic tractability.

The present work fits into this latter direction. By exploiting the algebraic structure of a finite group alphabet and the endomorphism property of the global rule, we identify a new, natural class of one-dimensional cellular automata for which topological entropy becomes effectively computable. Our results also settle questions left open in the literature. In [8] the computation of the topological entropy of a GCA was reduced to the case of alphabets that are either elementary abelian groups (Z/pZ)n(\mathbb{Z}/p\mathbb{Z})^n or products of isomorphic non-abelian simple groups, and was carried out only in the surjective non-abelian case; the abelian case is treated here (Theorem 4), while the non-surjective non-abelian case is avoided by a refinement of the decomposition, based on normal F\mathcal{F}-invariant subgroups instead of fully invariant ones (Lemma 11). In higher dimensions, Shereshevsky [39] showed that a cellular automaton on the two-dimensional full shift cannot be expansive, and conjectured that its topological entropy is either 00 or +∞+\infty (see [34]). For general CAs the conjecture does not hold, since in every dimension D≥2D \ge2 there exist CAs with finite positive entropy [33]. Morris and Ward pointed out that a special case of the conjecture concerns CAs which are endomorphisms of the group structure of the full shift; they formulated an algebraic analogue of the question and answered it for mixing endomorphisms of compact abelian groups commuting with a completely positive entropy Zd\mathbb{Z}^d-action [34]. Theorem 6 settles this special case in every dimension D≥2D \ge2, for every finite group alphabet and without any mixing assumption: the topological entropy of a DD-GCA is either 00 or +∞+\infty.

In this paper we focus on group cellular automata (GCAs). Let GG be a finite group. The full shift GZG^{\mathbb{Z}} inherits a natural group structure via component-wise multiplication, and a GCA is a CA whose global map F:GZ→GZ\mathcal{F}:G^{\mathbb{Z}}\to G^{\mathbb{Z}} is a group endomorphism. Such systems arise naturally in the study of algebraic dynamics and have been systematically investigated in the literature [4, 8, 14].

Our main result shows that the algebraic constraints imposed by the group structure lead to a strong structural simplification of the entropy computation. We introduce two families of finite objects that capture, separately, the left-moving and right-moving information in space-time. More precisely, for each time tt we consider the sets of left and right traces T−(F,t)T^{-}(\mathcal{F},t) and T+(F,t)T^{+}(\mathcal{F},t) obtained by evolving configurations that are trivial on one side. We then define two one-sided growth rates

H−(F)=lim⁡t→∞log⁡∣T−(F,t)∣t,H+(F)=lim⁡t→∞log⁡∣T+(F,t)∣t,\mathcal{H}^{-}(\mathcal{F})=\lim_{t\to\infty}\frac{\log\left|T^{-}(\mathcal{F},t)\right|}{t},\qquad\mathcal{H}^{+}(\mathcal{F})=\lim_{t\to\infty}\frac{\log\left|T^{+}(\mathcal{F},t)\right|}{t},

and we prove (Theorems 1 and 2) that for every one-dimensional group cellular automaton F\mathcal{F} on a finite group alphabet GG, the topological entropy satisfies

H(F)=H−(F)+H+(F).\mathcal{H}(\mathcal{F}) = \mathcal{H}^{-}(\mathcal{F}) + \mathcal{H}^{+}(\mathcal{F}).

As a consequence, the topological entropy is completely determined by the growth rate of a fixed width family of space-time patterns, denoted by T(F,t,0)T(\mathcal{F},t,0), arising in the evolution of the automaton. This reduction from arbitrarily large space-time windows to a uniformly bounded width yields an effective procedure for computing the topological entropy (Theorem 3). We also show that the topological entropy of a one-dimensional GCA is always the logarithm of a positive integer dividing ∣G∣lF+rF|G|^{l_{\mathcal{F}}+r_{\mathcal{F}}}, where lFl_{\mathcal{F}} and rFr_{\mathcal{F}} are the left and right radii of F\mathcal{F} (Corollary 1).

In Section 5 we turn to linear GCAs over (Z/pZ)n(\mathbb{Z}/p\mathbb{Z})^{n}, whose global rule is described by a matrix MM of Laurent polynomials. Following the algebraic approach of Akın, Dikranjan, Giordano Bruno and Toller [2], we pass to the Pontryagin dual, on which the dual of the automaton acts on the discrete group of finite configurations, and we use the Bridge Theorem [15, 42] relating topological and algebraic entropy. The algebraic entropy turns out to be the rank of a module over the polynomial ring Fp[t]\mathbb{F}_{p}[t], which can be read off the characteristic polynomial χM\chi_{M} of MM. In dimension one this yields

H(F)=(EM+−EM−)log⁡p,\mathcal{H}(\mathcal{F}) = (E_{M}^{+} - E_{M}^{-}) \log p,

where [EM−,EM+][E_{M}^{-},E_{M}^{+}] is the smallest interval containing 00 and all exponents appearing in the coefficients of χM\chi_{M} (Theorem 4); in dimension D≥2D \ge2 the entropy is either 00 or +∞+\infty. Combined with a refinement of the decomposition of GCAs introduced in [8], this provides a second, explicit, proof of the computability of the topological entropy of one-dimensional GCAs (Remark 2). Finally, we prove that a DD-dimensional GCA, with D≥2D \ge2, is either equicontinuous with zero topological entropy, or sensitive to initial conditions with infinite topological entropy (Theorem 6). As a consequence, the topological entropy of group cellular automata is computable in every dimension (Corollary 4). Finally, we give an explicit algorithm, running in polynomial time for every fixed dimension, which computes the topological entropy of a GCA from its local rule (Theorem 8).

The paper is organized as follows. Section 2 recalls the basic definitions of CAs and GCAs in arbitrary dimension. In Section 3 we review topological entropy and its space-time characterization for cellular automata. Section 4 contains the proof of the decomposition theorem and the resulting computability statement. Section 5 contains the explicit formula for linear GCAs over (Z/pZ)n(\mathbb{Z}/p\mathbb{Z})^{n} in every dimension. Section 6 deals with DD-dimensional GCAs, D≥2D \ge2. Section 7 analyzes the computational complexity of the resulting procedure.

CAs and GCAs

In this section, we review the fundamental definitions and key results related to CAs and GCAs. For additional definitions and results, we refer the reader to those introduced in [14]. We give the definitions in an arbitrary dimension D≥1D \ge1; at the beginning of each of the following sections we specify whether the dimension is arbitrary or D=1D = 1.

Configurations. Let D≥1D \ge1 be an integer and let GG be a finite set. A (DD-dimensional) configuration is any function from ZD\mathbb{Z}^{D} to GG, i.e., an element of GZDG^{\mathbb{Z}^{D}}. Given a configuration c∈GZDc \in G^{\mathbb{Z}^{D}} and v∈ZDv \in\mathbb{Z}^{D}, the value of cc at position vv is denoted by cvc_v, and for B⊆ZDB \subseteq\mathbb{Z}^{D} we denote by c∣Bc|_{B} the restriction of cc to BB. For v∈ZDv \in\mathbb{Z}^{D} we let ∥v∥∞=max⁡i∣vi∣\lVert v\rVert_{\infty} = \max_i |v_i|, and for w≥0w \ge0 we let Bw=[−w,w]DB_w = [-w,w]^{D}. We equip GZDG^{\mathbb{Z}^{D}} with the prodiscrete topology, that is, the product topology obtained by endowing each factor GG with the discrete topology. With this topology, GZDG^{\mathbb{Z}^{D}} is a compact topological space. Since GG is finite, GZDG^{\mathbb{Z}^{D}} is also metrizable. Indeed, the set GZDG^{\mathbb{Z}^{D}} can be equipped with the standard Tychonoff distance dd defined as

∀c,c′∈GZD:d(c,c′)={0if c=c′2−Δ(c,c′)otherwise\forall c,c' \in G^{\mathbb{Z}^{D}}:\quad d(c,c') = \begin{cases} 0 & \text{if } c=c'\\ 2^{-\Delta(c,c')} & \text{otherwise} \end{cases}

where Δ(c,c′)=min⁡{∥j∥∞:j∈ZD and cj≠cj′}\Delta(c,c') = \min\{\lVert j\rVert_{\infty}: j \in\mathbb{Z}^{D}\ \text{and}\ c_j \ne c'_j\}. The topology induced by the Tychonoff distance coincides with the prodiscrete topology. Note that d(c,c′)<2−wd(c,c') < 2^{-w} if and only if cc and c′c' coincide on BwB_w. For a finite set B⊆ZDB \subseteq\mathbb{Z}^{D} and u∈GBu \in G^{B}, the cylinder determined by uu is the set

Cyl(B,u)={c∈GZD:c∣B=u}.Cyl(B,u) = \{c \in G^{\mathbb{Z}^{D}} : c|_{B} = u\}.

Cylinders are clopen and form a basis of the prodiscrete topology; in particular, for every c∈GZDc \in G^{\mathbb{Z}^{D}} and w≥0w \ge0, the open ball of radius 2−w2^{-w} centered at cc is the cylinder Cyl(Bw,c∣Bw)Cyl(B_w,c|_{B_w}).

Cellular automata. For w∈ZDw \in\mathbb{Z}^{D}, the shift σw:GZD→GZD\sigma^{w}:G^{\mathbb{Z}^{D}} \to G^{\mathbb{Z}^{D}} is defined by

∀c∈GZD, ∀v∈ZD:σw(c)v=cv+w.\forall c \in G^{\mathbb{Z}^{D}},\ \forall v \in\mathbb{Z}^{D}:\quad\sigma^{w}(c)_v = c_{v+w}.

A (DD-dimensional) CACA on GG is any continuous function F:GZD→GZD\mathcal{F}:G^{\mathbb{Z}^{D}} \to G^{\mathbb{Z}^{D}} which is also shift commuting, i.e., F∘σw=σw∘F\mathcal{F} \circ\sigma^{w} = \sigma^{w} \circ\mathcal{F} for every w∈ZDw \in\mathbb{Z}^{D}. By the Curtis-Hedlund-Lyndon theorem [23], any CACA can be equivalently defined by means of a local rule f:Gk→Gf:G^{k} \to G together with a finite set Vf={v1,…,vk}⊆ZDV_f = \{v_1,\ldots,v_k\} \subseteq\mathbb{Z}^{D} of pairwise distinct vectors, called the neighborhood, as follows:

∀c∈GZD, ∀v∈ZD:F(c)v=f(cv+v1,…,cv+vk).\forall c \in G^{\mathbb{Z}^{D}},\ \forall v \in\mathbb{Z}^{D}:\quad\mathcal{F}(c)_v = f(c_{v+v_1},\ldots,c_{v+v_k}).

References

  1. [1]Roy L. Adler, Alan G. Konheim, and M. H. McAndrew. Topological entropy. Transactions of the American Mathematical Society, 114:309–319, 1965.
  2. [2]Hasan Akın, Dikran Dikranjan, Anna Giordano Bruno, and Daniele Toller. The algebraic entropy of one-dimensional finitary linear cellular automata. Journal of Group Theory, 27(4):813–856, 2024.arxiv.org/abs/2306.10838
  3. [3]Petre Anghelescu, Silviu Ionita, and Emil Sofron. Block encryption using hybrid additive cellular automata. In Andreas König, Mario Köppen, Nikola K. Kasabov, and Ajith Abraham, editors, 7th International Conference on Hybrid Intelligent Systems, HIS 2007, Kaiserslautern, Germany, September 17-19, 2007, pages 132–137. IEEE Computer Society, 2007.DOI
  4. [4]Pierre Béaur and Jarkko Kari. Effective projections on group shifts to decide properties of group cellular automata. Int. J. Found. Comput. Sci., 35(1&2):77–100, 2024.arxiv.org/abs/2301.11133
  5. [5]Stuart J. Berkowitz. On computing the determinant in small parallel time using a small number of processors. Information Processing Letters, 18(3):147–150, mar 1984.DOI
  6. [6]François Blanchard. Topological chaos: what may this mean? Journal of Difference Equations and Applications, 15(1):23–46, 2009.arxiv.org/abs/0805.0232
  7. [7]Rufus Bowen. Entropy for group endomorphisms and homogeneous spaces. Transactions of the American Mathematical Society, 153:401–414, 1971.DOI
  8. [8]Niccolò Castronuovo, Alberto Dennunzio, and Luciano Margara. A divide and conquer algorithm for deciding group cellular automata dynamics. Journal of Computer and System Sciences, 157:103749, 2026.arxiv.org/abs/2507.09761
  9. [9]Tullio Ceccherini-Silberstein and Michel Coornaert. Cellular Automata and Groups. Springer, 2010.
  10. [10]Michele d’Amico, Giovanni Manzini, and Luciano Margara. On computing the entropy of cellular automata. Theoretical Computer Science, 290(3):1629–1646, 2003.
  11. [11]Angel Martín del Rey, Joaquim Pereira Mateus, and Gerardo Rodríguez Sánchez. A secret sharing scheme based on cellular automata. Applied Mathematics and Computation, 170(2):1356–1364, 2005.DOI
  12. [12]Alberto Dennunzio, Enrico Formenti, Darij Grinberg, and Luciano Margara. Decidable characterizations of dynamical properties for additive cellular automata over a finite abelian group with applications to data encryption. Information Sciences, 563:183–195, 2021.DOI
  13. [13]Alberto Dennunzio, Enrico Formenti, and Luciano Margara. An easy to check characterization of positive expansivity for additive cellular automata over a finite abelian group. IEEE Access, 11:121246–121255, 2023.DOI
  14. [14]Alberto Dennunzio, Enrico Formenti, and Luciano Margara. On the dynamical behavior of cellular automata on finite groups. IEEE Access, 12:122061–122077, 2024.DOI
  15. [15]Dikran Dikranjan and Anna Giordano Bruno. The connection between topological and algebraic entropy. Topology and its Applications, 159(13):2980–2989, 2012.DOI
  16. [16]Dikran Dikranjan and Manuel Sanchis. Dimension and entropy in compact topological groups. Journal of Mathematical Analysis and Applications, 476(2):337–366, 2019.DOI
  17. [17]E. I. Dinaburg. On the relations among various entropy characteristics of dynamical systems. Mathematics of the USSR-Izvestiya, 5(2):337–378, 1971.DOI
  18. [18]D.S. Dummit and R.M. Foote. Abstract Algebra. Wiley, 3rd edition, 2003.
  19. [19]Anna Giordano Bruno and Luigi Salce. A soft introduction to algebraic entropy. Arabian Journal of Mathematics, 1:69–87, 2012.DOI
  20. [20]T. N. T. Goodman. Relating topological entropy and measure entropy. Bulletin of the London Mathematical Society, 3(2):176–180, 1971.DOI
  21. [21]Pierre Guillon and Charalampos Zinoviadis. Densities and entropies in cellular automata. In How the World Computes: Turing Centenary Conference and 8th Conference on Computability in Europe (CiE 2012), volume 7318 of Lecture Notes in Computer Science, pages 253–263. Springer, 2012.arxiv.org/abs/1204.0949
  22. [22]Karl-Peter Hadeler and Johannes Müller. Cellular Automata: Analysis and Applications. Springer Monographs in Mathematics. Springer, 2017.DOI
  23. [23]Gustav A. Hedlund. Endomorphisms and automorphisms of the shift dynamical system. Mathematical Systems Theory, 3:320–375, 1969.DOI
  24. [24]Toni Hotanen. Undecidability of the topological entropy of reversible cellular automata and related problems. In Daniela Genova and Jarkko Kari, editors, Unconventional Computation and Natural Computation (UCNC 2023), volume 14003 of Lecture Notes in Computer Science, pages 108–123. Springer, 2023.DOI
  25. [25]T.W. Hungerford. Algebra. Graduate Texts in Mathematics. Springer New York, 2003.
  26. [26]Lyman Hurd, Jarkko Kari, and Karel Culik. The topological entropy of cellular automata is uncomputable. Ergodic Theory and Dynamical Systems, 12(2):255–265, 1992.DOI
  27. [27]Jarkko Kari. Linear cellular automata with multiple state variables. In Horst Reichel and Sophie Tison, editors, STACS 2000, volume 1770 of LNCS, pages 110–121. Springer-Verlag, 2000.DOI
  28. [28]Jarkko Kari. Cellular automata. Lecture notes, University of Turku, 2024.
  29. [29]Anatole Katok and Boris Hasselblatt. Introduction to the Modern Theory of Dynamical Systems. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 1995.
  30. [30]Bruce Kitchens and Klaus Schmidt. Automorphisms of compact groups. Ergodic Theory and Dynamical Systems, 9(4):691–735, 1989.DOI
  31. [31]Bruce P. Kitchens. Expansive dynamics on zero-dimensional groups. Ergodic Theory and Dynamical Systems, 7(2):249–261, 1987.DOI
  32. [32]Douglas Lind and Brian Marcus. An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, 1995.DOI
  33. [33]Tom Meyerovitch. Finite entropy for multidimensional cellular automata. Ergodic Theory and Dynamical Systems, 28(4):1243–1260, 2008.arxiv.org/abs/math/0703167
  34. [34]G. Morris and T. Ward. Entropy bounds for endomorphisms commuting with k actions. Israel Journal of Mathematics, 106(1):1–12, 1998.
  35. [35]C. Fraile Rubio, Luis Hernández Encinas, Sara Hoya White, Ángel Martín del Rey, and Gerardo Rodríguez Sánchez. The use of linear hybrid cellular automata as pseudo random bit generators in cryptography. Neural Parallel & Scientific Computing, 12(2):175–192, 2004.
  36. [36]Luigi Salce, Peter Vámos, and Simone Virili. Length functions, multiplicities and algebraic entropy. Forum Mathematicum, 25(2):255–282, 2013.
  37. [37]Jacob T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM, 27(4):701–717, 1980.DOI
  38. [38]M. A. Shereshevsky. Lyapunov exponents for one-dimensional cellular automata. Journal of Nonlinear Science, 2:1–8, 1992.DOI
  39. [39]M. A. Shereshevsky. Expansiveness, entropy and polynomial growth for groups acting on subshifts by automorphisms. Indagationes Mathematicae (N.S.), 4(2):203–210, 1993.DOI
  40. [40]John von Neumann. Theory of Self-Reproducing Automata. University of Illinois Press, 1966. Edited and completed by Arthur W. Burks.DOI
  41. [41]Peter Walters. An Introduction to Ergodic Theory, volume 79 of Graduate Texts in Mathematics. Springer-Verlag, 1982.
  42. [42]Michael D. Weiss. Algebraic and other entropies of group endomorphisms. Mathematical Systems Theory, 8(3):243–248, 1974.DOI
  43. [43]Stephen Wolfram. Statistical mechanics of cellular automata. Reviews of Modern Physics, 55:601–644, 1983.
  44. [44]S. A. Yuzvinskiĭ. Metric properties of endomorphisms of compact groups. Izvestiya Akademii Nauk SSSR. Seriya Matematicheskaya, 29:1295–1328, 1965. English translation: Amer. Math. Soc. Transl. Ser. 2, 66 (1968), 63–98.
  45. [45]Richard Zippel. Probabilistic algorithms for sparse polynomials. In Symbolic and Algebraic Computation (EUROSAM ’79), volume 72 of Lecture Notes in Computer Science, pages 216–226. Springer, 1979.DOI

Paper details

vlnc:W_f58bscaq
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 11

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents