Directional Entropies of Cellular Automaton-Maps

• John Milnor
Conference paper
Part of the NATO ASI Series book series (volume 20)

Abstract

Consider a fixed lattice L in n -dimensional euclidean space, and a finite set K of symbols. A correspondence a which assigns a symbol a(x) ∈K to each lattice point xL will be called a configuration. An n -dimensional cellular automaton can be described as a map which assigns to each such configuration a some new configuration a′ = f (a) by a formula of the form
$$a'(x) = F(a(x + {v_l}),...,\,a(x + {v_{\tau }}))$$
a’(x) = F(a(x + v 1)), ⋯, a(x + v r)), where v 1, ⋯, v r are fixed vectors in the lattice L, and where F is a fixed function of r symbols in K. I will call f the cellular automaton-map which is associated with the local map F. If the alphabet K has k elements, then the number of distinct local maps F is equal to k k′ . This is usually an enormous number, so that it is not possible to examine all of the possible F. Depending on the particular choice of F and of the v 1, such an automaton may display behavior which is simple and convergent, or chaotic and random looking, or behavior which is very complex and difficult to describe. (Compare [Wolfram].)

Keywords

Cellular Automaton Topological Entropy Dimensional Euclidean Space High Dimensional Case Fixed Lattice
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

References

1. AMOROSO S. and PATT Y. N. (1972): Decision procedure for surjectivity and injectivity of parallel maps for tessellation structures, J. Comp. Syst. Sci. 6, 448–464.
2. BOYLE M. and KRIEGER W. (to appear): Periodic points and automorphisms of the shift.Google Scholar
3. COVEN E. M. (1980): Topological entropy of block maps, Proc. Amer. Math. Soc. 78, pp 590–594.
4. DEMONGEOT J., GOLES E. and TCHUENTE M. (1985): Dynamical systems and cellular automata, Academic Press.
5. FRIED D. (1983): Entropy for smooth abelian actions, Proc. Amer. Math. Soc. 87, pp 111–116.
6. GOODWYN L. W. (1972): Some counter-examples in topological entropy, Topology 11, pp 377–385.
7. HEDLUND G. A. (1969): Endomorphisms and automorphisms of the shift dynamical system, Math. Syst. Th. 3, pp 320–375.
8. LIND D. and SMILLIE J. (in preparation).Google Scholar
9. MARUOKA A. and KIMURA M. (1976): Condition for injectivity of global maps for tessellation automata, Inform. and Contr. 32, 158–162.
10. SINAI YA. (to appear): On a question of J. Milnor, Comment. Math. Helv.Google Scholar
11. WALTERS P. (1975): Ergodic Theory — Introductory Lectures, Lecture Notes in Math. 458, Springer.Google Scholar
12. WOLFRAM S. (1984): Universality and complexity in cellular automata, Physica 10D, pp 1–35; Cellular automata as models of complexity, Nature 311, pp 419–424.
13. YAKU T. (1973): The constructibility of a configuration in a cellular automaton, J. Comp. and System Sci. 7, pp 481–496.