Entropy of multidimensional cellular automata

DOI10.1134/S0032946006010042MaRDI QIDQ2498321zbMATH OpenFDO

Authors E. S. Langvagen, E. Lakshtanov

Publication date 16 August 2006

Published in Problems of Information Transmission (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1134/S0032946006010042

zbMATH Keywords

asymptotics of the information functioncellular automatoncomplexityrenormalizationtopological entropy

Mathematics Subject Classification ID

Dynamical aspects of cellular automata (37B15) Topological entropy (37B40) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Review text

Since the topological entropy of a vast class of two-dimensional cellular automata (CA) is infinite, it is of interest the possibility to renormalize the topological entropy so that we obtain a positive finite value. We find the asymptotics of the information function of a multidimensional CA and, accordingly, introduce the renormalized topological entropy as a coefficient of this asymptotics. We describe some properties of the introduced quantity, in particular, its positivity for CA of the type of ``The Game of Life. Also, we give an example of an explicit evaluation of this parameter for a particular cellular automaton.

Recommendations

• Finite entropy for multidimensional cellular automata
• scientific article; zbMATH DE number 4100614
• scientific article; zbMATH DE number 1223725
• Densities and entropies in cellular automata
• Entropy of additive cellular automata
• Apparent entropy of cellular automata
• Rescaled entropy of cellular automata
• Directional entropies of cellular automaton-maps
• On computing the entropy of cellular automata.

Cites work

• Criterion of infinite topological entropy for multidimensional cellular automata
• Directional entropies of cellular automaton-maps
• scientific article; zbMATH DE number 776267 (Why is no real title available?)
• On computing the entropy of cellular automata.
• Upper and lower bounds for the Kolmogorov entropy of the attractor for the RDE in an unbounded domain

Cited in

(13)

• On the law of entropy increase of some cellular automata on \(\mathbb{Z}^d\)
• Arithmetic representations of cellular automata
• Development of concept of topological entropy for systems with multiple time
• Development of the topological entropy conception for dynamical systems with multiple time
• Estimation of topological entropy for cocycles with cellular automaton as a base system
• Minimal entropy approximation for cellular automata
• Finite entropy for multidimensional cellular automata
• scientific article; zbMATH DE number 4100614 (Why is no real title available?)
• scientific article; zbMATH DE number 12463 (Why is no real title available?)
• scientific article; zbMATH DE number 614592 (Why is no real title available?)
• Rescaled entropy of cellular automata
• k-Mixing Properties of Multidimensional Cellular Automata
• Apparent entropy of cellular automata

This page was built for publication: Entropy of multidimensional cellular automata

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