Abstract
We introduce a local version of the Shannon entropy in order to describe information transport in spatially extended dynamical systems, and to explore to what extent information can be viewed as a local quantity. Using an appropriately defined information current, this quantity is shown to obey a local conservation law in the case of one-dimensional reversible cellular automata with arbitrary initial measures. The result is also shown to apply to one-dimensional surjective cellular automata in the case of shift-invariant measures. Bounds on the information flow are also shown.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bennett C.H. (1973). Logical reversibility of computation. IBM J. Res. Develop. 17(6): 525–532
Dab D., Lawniczak A., Boon J.P., Kapral R. (1990). Cellular-automaton model for reactive systems. Phys. Rev. Lett. 64: 2462–2465
Ferrari P., Maass A., Martínez S., Ney P. (2000). Cesàro mean distribution of group automata starting from measures with summable decay. Ergodic Theory Dynam. Systems. 20(6): 1657–1670
Frisch U., Hasslacher B., Pomeau Y. (1986). Lattice-gas automata for the Navier-Stokes equation. Phys. Rev. Lett. 56: 1505–1508
Gänssler, P., Stute, W. (1977). Wahrscheinlichkeitstheorie. Springer Verlag, Berlin Heidelberg New York
Gray R.M. (1988). Probability, random processes and ergodic properties. Springer-Verlag, New York
Hardy J., Pomeau Y., de Pazzis O. (1973). Time evolution of two-dimensional model system. I. invariant states and time correlation functions. J. Math. Phys. 14: 1746–1759
Hedlund G.A. (1969). Endomorphisms and automorphisms of the shift dynamical system. Math. Syst. Theory. 3: 320–375
Host B., Maass A., Martínez S. (2003). Uniform Bernoulli measure in dynamics of permutative cellular automata with algebraic local rules. Discrete Contin. Dyn. Syst. 9(6): 1423–1446
Ito M., Osato N., Nasu M. (1983). Linear cellular automata over Zm. J. Comput. System Sci. 27(2): 125–140
Jaynes E.T. (1957). Information theory and statistical mechanics. Phys. Rev. 106: 620–630
Keller G. (1998). Equilibrium states in ergodic theory, Volume 42 of London Mathematical Society Student Texts. Cambridge University Press, Cambridge
Kullback S., Leibler R.A. (1951). On information and sufficiency. Ann. Math. Stat. 22: 79–86
Landauer R. (1961). Irreversibility and heat generation in the computing process. IBM J. Res. Develop. 5(3): 183–191
Lind D.A. (1984). Applications of ergodic theory and sofic systems to cellular automata. Physica D. 10: 36–44
Lindgren K. (1987). Correlations and random information in cellular automata. Complex Systems. 1: 529–543
Lindgren K. (1988). Microscopic and macroscopic entropy. Phys. Rev. A. 38: 4794–4798
Pivato M., Yassawi R. (2002). Limit measures for affine cellular automata. Ergodic Theory Dynam. Systems. 22(4): 1269–1287
Pivato M., Yassawi R. (2004). Limit measures for affine cellular automata II. Ergodic Theory Dynam. Systems. 24(6): 1961–1980
Richardson D. (1972). Tesselations with local transformations. J. Comput. System Sci. 5: 373–388
Takesue S. (1987). Reversible cellular automata and statistical mechanics. Phys. Rev. Lett. 59: 2499–2502
Takesue S. (1990). Fourier’s law and the Green-Kubo formula in a cellular-automaton model. Phys. Rev. Lett. 64: 252–255
Toffoli T. (1988). Information transport obeying the continuity equation. IBM J. Res. Develop. 32(1): 29–36
Toffoli T., Margolus N.H. (1990). Invertible cellular automata: a review. Physica D. 45(1–3): 229–253
Vichniac G. (1984). Simulating physics with cellular automata. Physica D. 10: 96–115
Walters P. (1982). An Introduction to Ergodic Theory. Number 79 in Graduate Texts in Mathematics. Springer, Berlin Heidelberg New York
Wheeler J.A. (1989). Information, physics, quantum: The search for links. In: Zurek, WH (eds) Complexity, Entropy and the Physics of Information. Addison-Wesley, Redwood City, CA
Zurek W.H. (1989). Algorithmic randomness and physical entropy. Phys. Rev. A. 40: 4731–4751
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by G. Gallavotti
Rights and permissions
About this article
Cite this article
Helvik, T., Lindgren, K. & Nordahl, M.G. Continuity of Information Transport in Surjective Cellular Automata. Commun. Math. Phys. 272, 53–74 (2007). https://doi.org/10.1007/s00220-007-0192-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00220-007-0192-8