Finite entropy for multidimensional cellular automata

DOI10.1017/S0143385707000855MaRDI QIDQ3528760zbMATH OpenOpenAlexFDO

Authors Tom Meyerovitch

Publication date 17 October 2008

Published in Ergodic Theory and Dynamical Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0703167

zbMATH Keywords

cellular automatatiling systemtopological entropy

Mathematics Subject Classification ID

Dynamical aspects of cellular automata (37B15)

Abstract: Let $X=S^G$ where $G$ is a countable group and $S$ is a finite set. A cellular automaton (CA) is an endomorphism $T:XoX$ (continuous, commuting with the action of $G$). Shereshevsky (1993) proved that for $G=Z^d$ with $d>1$ no CA can be forward expansive, raising the following conjecture: For $G=Z^d$, $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).

Recommendations

• scientific article; zbMATH DE number 4100614
• On computing the entropy of cellular automata.
• scientific article; zbMATH DE number 1223725
• Entropy of multidimensional cellular automata
• Rescaled entropy of cellular automata

Cites work

• Cellular automata: From a theoretical parallel computational model to its application to complex systems
• Endomorphisms and automorphisms of the shift dynamical system
• Entropy bounds for endomorphisms commuting with \(k\) actions
• Ergodic theory on compact spaces
• Expansiveness, entropy and polynomial growth for groups acting on subshifts by automorphisms
• Matching rules and substitution tilings
• On computing the entropy of cellular automata.
• On multidimensional curves with Hilbert property
• Reversibility and surjectivity problems of cellular automata
• Theory of cellular automata: a survey
• Topological and measure-theoretic properties of one-dimensional cellular automata
• Undecidability and nonperiodicity for tilings of the plane

Cited in

(13)

• On the conjugacy problem of cellular automata
• Amenability of groups is characterized by Myhill's theorem
• Entropy of multidimensional cellular automata
• Minimal entropy approximation for cellular automata
• Multidimensional cellular automata: closing property, quasi-expansivity, and (un)decidability issues
• scientific article; zbMATH DE number 12463 (Why is no real title available?)
• Amenability of groups and G-sets
• Rescaled entropy of cellular automata
• scientific article; zbMATH DE number 7384886 (Why is no real title available?)
• The entropy and reversibility of cellular automata on Cayley tree
• Dynamics and topological entropy of 1D Greenberg-Hastings cellular automata
• Growth-type invariants for \(\mathbb Z^{d}\) subshifts of finite type and arithmetical classes of real numbers
• Gardens of Eden and amenability on cellular automata

This page was built for publication: Finite entropy for multidimensional cellular automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3528760)