On the hierarchy of conservation laws in a cellular automaton. (English) Zbl 1251.68148
Summary: Conservation laws in cellular automata (CA) are studied as an abstraction of the conservation laws observed in nature. In addition to the usual real-valued conservation laws we also consider more general group-valued and semigroup-valued conservation laws. The (algebraic) conservation laws in a CA form a hierarchy, based on the range of the interactions they take into account. The conservation laws with smaller interaction ranges are the homomorphic images of those with larger interaction ranges, and for each specific range there is a most general law that incorporates all those with that range. For one-dimensional CA, such a most general conservation law has – even in the semigroup-valued case – an effectively constructible finite presentation, while for higher-dimensional CA such effective construction exists only in the group-valued case. It is even undecidable whether a given two-dimensional CA conserves a given semigroup-valued energy assignment. Although the local properties of this hierarchy are tractable in the one-dimensional case, its global properties turn out to be undecidable. In particular, we prove that it is undecidable whether this hierarchy is trivial or unbounded. We point out some interconnections between the structure of this hierarchy and the dynamical properties of the CA. In particular, we show that positively expansive CA do not have non-trivial real-valued conservation laws.
Keywords:
cellular automata; conservation laws; energy; reversibility; undecidability; dynamical systems; chaosReferences:
| [1] | Biryukov AP (1967) Some algorithmic problems for finitely defined commutative semigroups. Sib Math J 8:384–391 · Zbl 0223.20064 · doi:10.1007/BF02196421 |
| [2] | Blondel VD, Cassaigne J, Nichitiu C (2002) On the presence of periodic configurations in turing machines and in counter machines. Theor Comput Sci 289:573–590 · Zbl 1061.68050 · doi:10.1016/S0304-3975(01)00382-6 |
| [3] | Boccara N, Fukś H (1998) Cellular automaton rules conserving the number of active sites. J Phys A 31:6007–6018 · Zbl 0981.37002 · doi:10.1088/0305-4470/31/28/014 |
| [4] | Conway JH, Lagarias JC (1990) Tiling with polyominoes and combinatorial group theory. J Comb Theory A 53:183–208 · Zbl 0741.05019 · doi:10.1016/0097-3165(90)90057-4 |
| [5] | Durand B, Formenti E, Róka Z (2003) Number conserving cellular automata I: decidability. Theor Comput Sci 299:523–535 · Zbl 1042.68076 · doi:10.1016/S0304-3975(02)00534-0 |
| [6] | Finelli M, Manzini G, Margara K (1998) Lyapunov exponents versus expansivity and sensitivity in cellular automata. J Complex 14:210–233 · Zbl 0920.68093 · doi:10.1006/jcom.1998.0474 |
| [7] | Formenti E, Grange A (2003) Number conserving cellular automata II: dynamics. Theor Comput Sci 304:269–290 · Zbl 1045.68094 · doi:10.1016/S0304-3975(03)00134-8 |
| [8] | Formenti E, Kari J, Taati S (2008) The most general conservation law for a cellular automaton. In: Hirsch EA, Razborov AA, Semenov AL, Slissenko A (eds) CSR vol 5010 of Lecture notes in computer science. Springer, New York, pp 194–203 · Zbl 1142.68443 |
| [9] | Fukś H (2000) A class of cellular automata equivalent to deterministic particle systems. In: Feng S, Lawniczak AT, Varadhan SRS (eds) Hydrodynamic limits and related topics, vol 27 of Fields institute communications. American Mathematical Society, Providence, pp 57–69 · Zbl 1065.37009 |
| [10] | Grillet PA (1995) Semigroups: an introduction to the structure theory. Dekker, New York · Zbl 0874.20039 |
| [11] | Hardy J, de Pazzis O, Pomeau Y (1976) Molecular dynamics of a classical lattice gas: transport properties and time correlation functions. Phys Rev A 13:1949–1961 · doi:10.1103/PhysRevA.13.1949 |
| [12] | Hattori T, Takesue S (1991) Additive conserved quantities in discrete-time lattice dynamical systems. Physica D 49:295–322 · Zbl 0755.58020 · doi:10.1016/0167-2789(91)90150-8 |
| [13] | Hedlund GA (1969) Endomorphisms and automorphisms of the shift dynamical system. Math Syst Theory 3:320–375 · Zbl 0182.56901 · doi:10.1007/BF01691062 |
| [14] | Kari J (1994) Reversibility and surjectivity problems of cellular automata. J Comput Syst Sci 48:149–182 · Zbl 0802.68090 · doi:10.1016/S0022-0000(05)80025-X |
| [15] | Kari J (2000) Linear cellular automata with multiple state variables. In: Reichel H, Tison S (eds) STACS vol 1770 of Lecture notes in computer science. Springer, New York, pp 110–121 · Zbl 0959.68085 |
| [16] | Kari J (2005) Theory of cellular automata: a survey. Theor Comput Sci 334:3–33 · Zbl 1080.68070 · doi:10.1016/j.tcs.2004.11.021 |
| [17] | Kurka P (1997) Languages, equicontinuity and attractors in cellular automata. Ergod Theory Dyn Syst 17:417–433 · Zbl 0876.68075 · doi:10.1017/S014338579706985X |
| [18] | Kurka P (2003) Topological and symbolic dynamics, vol 11 of Cours Spécialisés, Société Mathématique de France |
| [19] | Manzini G, Margara L (1999) A complete and efficiently computable topological classification of d-dimensional linear cellular automata over $${{\(\backslash\)mathbb{Z}}_m}.$$ Theor Comput Sci 221:157–177 · Zbl 0930.68090 · doi:10.1016/S0304-3975(99)00031-6 |
| [20] | Minsky M (1967) Computation: finite and infinite machines. Prentice-Hall, Englewood Cliffs · Zbl 0195.02402 |
| [21] | Moore EF (1962) Machine models of self-reproduction. In: Proceedings of symposia in applied mathematics. AMS, Providence, pp 17–33 · Zbl 0126.32408 |
| [22] | Moreira A, Boccara N, Goles E (2004) On conservative and monotone one-dimensional cellular automata and their particle representation. Theor Comput Sci 325:285–316 · Zbl 1071.68068 · doi:10.1016/j.tcs.2004.06.010 |
| [23] | Myhill J (1963) The converse of Moore’s garden-of-Eden theorem. Proc Am Math Soc 14:685–686 · Zbl 0126.32501 |
| [24] | Nasu M (1995) Textile systems for endomorphisms and automorphisms of the shift. Mem Am Math Soc 114, no. 546, pp viii + 215 · Zbl 0845.54031 |
| [25] | Pivato M (2002) Conservation laws in cellular automata. Nonlinearity 15:1781–1793 · Zbl 1013.37008 · doi:10.1088/0951-7715/15/6/305 |
| [26] | Pomeau Y (1984) Invariant in cellular automata. J Phys A 17:L415–L418 · Zbl 0537.68049 · doi:10.1088/0305-4470/17/8/004 |
| [27] | Robison AD (1987) Fast computation of additive cellular automata. Complex Syst 1:211–216 · Zbl 0655.68064 |
| [28] | Takesue S (1987) Reversible cellular automata and statistical mechanics. Phys Rev Lett 59:2499–2502 · doi:10.1103/PhysRevLett.59.2499 |
| [29] | Thurston WP (1990) Conway’s tiling groups. Am Math Mon 97:757–773 · Zbl 0714.52007 · doi:10.2307/2324578 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
