×

Highly symmetric cellular automata and their symmetry-breaking patterns. (English) Zbl 1076.37503

Summary: A highly symmetric cellular automaton (in one dimension) is defined by two properties: (i) its local rule is a completely symmetric function of the \(n\) cells of its surrounding and (ii) it is invariant with respect to a regular, Abelian group acting on its \(M\)-letter alphabet, which can then be identified with this group. The motivation for studying such systems is provided by the unsolved problem of partial symmetry breaking in spin models with such an Abelian symmetry. It is shown that the symmetries (i) and (ii) do not contradict each other if and only if \(n\) and \(M\) have no common factor. As examples, the four-letter alphabets, which may be identified either with the cyclic group \(C(4)\) or with the Klein group \(K(4)\cong S(2)\otimes S(2)\) are studied for the standard \(n=3\) surrounding. It is shown that these automata show complicated patterns of broken symmetries. These give information on the corresponding spin models, the chiral 4-state clock model and the (symmetric and general) Ashkin-Teller models, respectively.

MSC:

37B15 Dynamical aspects of cellular automata
82C20 Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics

Software:

avida
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] J. von Neumann, in: A. Burks (Ed.), Theory of Self-reproducing Automata, University of Illinois Press, Champaign, IL, 1966.; J. von Neumann, in: A. Burks (Ed.), Theory of Self-reproducing Automata, University of Illinois Press, Champaign, IL, 1966.
[2] S. Wolfram, Theory and Applications of Cellular Automata, Advanced Series in Complex Systems, Vol. 1, World Scientific, Singapore, 1986.; S. Wolfram, Theory and Applications of Cellular Automata, Advanced Series in Complex Systems, Vol. 1, World Scientific, Singapore, 1986.
[3] H. Gutowitz, Cellular Automata, MIT Press, Cambridge, MA, 1991.; H. Gutowitz, Cellular Automata, MIT Press, Cambridge, MA, 1991.
[4] R. Gaylord, K. Nishidate, Modeling Nature: Cellular Automata Simulations with Mathematica, Springer, New York, 1996.; R. Gaylord, K. Nishidate, Modeling Nature: Cellular Automata Simulations with Mathematica, Springer, New York, 1996. · Zbl 0860.68117
[5] C. Adami, Introduction to Artificial Life, Springer, New York, 1998.; C. Adami, Introduction to Artificial Life, Springer, New York, 1998. · Zbl 0902.68198
[6] Smith III, A. R., Simple computation-universal spaces, J. ACM, 18, 339-349 (1971) · Zbl 0221.94071
[7] Ising, E., Beitrag zur theorie des ferromagnetismus, Z. Phys., 31, 253-258 (1925) · Zbl 1439.82056
[8] Potts, R. B., Some generalized order-disorder transformations, Proc. Camb. Phil. Soc., 48, 106-109 (1952) · Zbl 0048.45601
[9] Ashkin, J.; Teller, E., Statistics of two-dimensional lattices with four components, Phys. Rev., 64, 178-184 (1943)
[10] H. Moraal, Classical, Discrete Spin Models, Lecture Notes in Physics, Vol. 214, Springer, Berlin, 1984.; H. Moraal, Classical, Discrete Spin Models, Lecture Notes in Physics, Vol. 214, Springer, Berlin, 1984.
[11] H. Moraal, High-temperature expansions for classical spin models. III. Series and phase diagrams for the square lattice, Physica A 197 (1993) 469-500.; H. Moraal, High-temperature expansions for classical spin models. III. Series and phase diagrams for the square lattice, Physica A 197 (1993) 469-500.
[12] Wolfram, S., Universality and complexity in cellular automata, Physica D, 10, 1-35 (1984)
[13] Wolfram, S., Computation theory of cellular automata, Commun. Math. Phys., 96, 15-57 (1984) · Zbl 0587.68050
[14] B. Huppert, Endliche Gruppen I, Springer, Berlin, 1963.; B. Huppert, Endliche Gruppen I, Springer, Berlin, 1963. · Zbl 0217.07201
[15] M. Hall Jr., The Theory of Groups, Chelsea, New York, 1976.; M. Hall Jr., The Theory of Groups, Chelsea, New York, 1976.
[16] Wolfram, S., Statistical mechanics of cellular automata, Rev. Mod. Phys., 55, 601-644 (1983) · Zbl 1174.82319
[17] Domany, E.; Riedel, E. K., Two-dimensional anisotropic N-vector models, Phys. Rev. B, 19, 5817-5834 (1979)
[18] Moraal, H., Graph-theoretical characterization of invertible cellular automata, Physica D, 141, 1-18 (2000) · Zbl 0970.68111
[19] Culik II, K.; Yu, S., Undecidability for CA classification schemes, Complex Syst., 2, 177-190 (1988) · Zbl 0657.68054
[20] W. Selke, Spatially modulated structures with competing interactions, in: C. Domb, J.L. Lebowitz (Eds.), Phase Transitions and Critical Phenomena, Vol. 15, Academic Press, New York, 1992, pp. 1-72.; W. Selke, Spatially modulated structures with competing interactions, in: C. Domb, J.L. Lebowitz (Eds.), Phase Transitions and Critical Phenomena, Vol. 15, Academic Press, New York, 1992, pp. 1-72.
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.