𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On computing the entropy of cellular automata

✍ Scribed by Michele D'amico; Giovanni Manzini; Luciano Margara

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
208 KB
Volume
290
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

We study the topological entropy of a particular class of dynamical systems: cellular automata. The topological entropy of a dynamical system (X; F) is a measure of the complexity of the dynamics of F over the space X . The problem of computing (or even approximating) the topological entropy of a given cellular automata is algorithmically undecidable (Ergodic Theory Dynamical Systems 12 (1992) 255). In this paper, we show how to compute the entropy of two important classes of cellular automata namely, linear and positively expansive cellular automata. In particular, we prove a closed formula for the topological entropy of D-dimensional (D ΒΏ 1) linear cellular automata over the ring Zm (m ΒΏ 2) and we provide an algorithm for computing the topological entropy of positively expansive cellular automata.

πŸ“œ SIMILAR VOLUMES

The topological entropy of invertible ce
The topological entropy of invertible cellular automata
✍ Hasan AkΔ±n πŸ“‚ Article πŸ“… 2008 πŸ› Elsevier Science 🌐 English βš– 159 KB

This paper is concerned with the topological entropy of invertible one-dimensional linear cellular automata, i.e., the maps T f [-r,r] : m and f : Z 2r+1 m β†’ Z m , over the ring Z m (m 2) by means of algorithm defined by D'amica et al. [On computing the entropy of cellular automa, Theoret. Comput.

On the Computational Complexity of Finit
On the Computational Complexity of Finite Cellular Automata
✍ K. Sutner πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 932 KB

We study the computational complexity of several problems with the evolution of configurations on finite cellular automata. In many cases, the problems turn out to be complete in their respective classes. For example, the problem of deciding whether a configuration has a predecessor is shown to be N

On the classifiability of cellular autom
On the classifiability of cellular automata
✍ John T. Baldwin; Saharon Shelah πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 106 KB

Based on computer simulations Wolfram presented in several papers conjectured classiΓΏcations of cellular automata into four types. We show a natural formalization of his rate of growth suggestion does not provide a classiΓΏcation (even probabilistically) of all cellular automata: For any rational p;