Directional Entropies of Cellular Automaton-Maps

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


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].)


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.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  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.zbMATHMathSciNetCrossRefGoogle Scholar
  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.zbMATHMathSciNetCrossRefGoogle Scholar
  4. DEMONGEOT J., GOLES E. and TCHUENTE M. (1985): Dynamical systems and cellular automata, Academic Press.zbMATHGoogle Scholar
  5. FRIED D. (1983): Entropy for smooth abelian actions, Proc. Amer. Math. Soc. 87, pp 111–116.zbMATHMathSciNetCrossRefGoogle Scholar
  6. GOODWYN L. W. (1972): Some counter-examples in topological entropy, Topology 11, pp 377–385.zbMATHMathSciNetCrossRefGoogle Scholar
  7. HEDLUND G. A. (1969): Endomorphisms and automorphisms of the shift dynamical system, Math. Syst. Th. 3, pp 320–375.zbMATHMathSciNetCrossRefGoogle Scholar
  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.zbMATHMathSciNetCrossRefGoogle Scholar
  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.CrossRefGoogle Scholar
  13. YAKU T. (1973): The constructibility of a configuration in a cellular automaton, J. Comp. and System Sci. 7, pp 481–496.zbMATHMathSciNetCrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 1986

Authors and Affiliations

  • John Milnor
    • 1
  1. 1.Institute for Advanced StudyPrincetonUSA

Personalised recommendations