2007/03/06 by Tom Meyerovitch, Meyerovitch, Tom
Computer Science · Mathematics · #37B15 #37B40 #37B50 #Cellular Automata and Applications #Computability, Logic, AI Algorithms #Dynamical Systems (math.DS) #FOS: Mathematics #Mathematical Dynamics and Fractals #math.DS #msc:37B15 #msc:37B40 #msc:37B50
paper · pdf · doi:10.48550/arxiv.math/0703167
17 pages, 11 figures; Added references, proposition 3.5 and correction of minor mistake in section 2
openalex publication_date 2007/03/06 · arxiv created 2007/05/30 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let X=SG where G is a countable group and S is a finite set. A cellular automaton (CA) is an endomorphism T : X → X (continuous, commuting with the action of G). Shereshevsky (1993) proved that for G=Zd with d>1 no CA can be forward expansive, raising the following conjecture: For G=Zd, d>1 the topological entropy of any CA is either zero or infinite. Morris and Ward (1998), proved this for linear CA's, leaving the original conjecture open. We show that this conjecture is false, proving that for any d there exist a d-dimensional CA with finite, nonzero topological entropy. We also discuss a measure-theoretic counterpart of this question for measure-preserving CA's. Our main tool is a construction of a CA by Kari (1994).