×

zbMATH — the first resource for mathematics

Applications of ergodic theory and sofic systems to cellular automata. (English) Zbl 0562.68038
Cellular automata, Proc. Interdisc. Workshop, Los Alamos/N.M. 1983, Physica D 10, No. 1-2, 36-44 (1984).
Summary: We indicate a mathematical framework for analysing the evolution of cellular automata. Those automata obeying an additive rule are shown to be the same as endomorphisms of a compact abelian group, and therefore their statistical and dynamical behavior can be told exactly by using Fourier analysis and ergodic theory. Those obeying certain nonlinear rules are closely tied to a finitely-described object called a sofic system, but the underlying statistics appear to be more complicated and interesting. We conclude by formulating several conjectures about one such system.
[For the entire collection see Zbl 0556.00013.]

MSC:
68Q80 Cellular automata (computational aspects)
37B15 Dynamical aspects of cellular automata
37A25 Ergodicity, mixing, rates of mixing
22D40 Ergodic theory on groups
22C05 Compact groups
References:
[1] Von Neumann, J.: A.w.burkstheory of self-reproducing automata. Theory of self-reproducing automata (1966)
[2] Wolfram, S.: Statistical mechanics of cellular automata. Rev. mod. Physics 55, 601-644 (1983) · Zbl 1174.82319
[3] P. Grassberger, A new mechanism for deterministic diffusion, Univ. of Wuppertal preprint. · Zbl 0562.68039
[4] Erdös, P.; Ney, P.: Ann. of prob.. 2, 828 (1974)
[5] Adelman, O.: Ann. inst. H. Poincaré. 12, 193 (1976)
[6] Willson, S. J.: Math. systems theory. 9, 132 (1975) · Zbl 0316.94057
[7] Lind, D.: Israel J. Math.. 28, 205 (1977)
[8] Weiss, B.: Monatsh. math.. 77, 462 (1973)
[9] Hedlund, G.: Math. systems theory. 3, 320 (1969)
[10] Lamperti, J.: Probability. (1966) · Zbl 0147.15502
[11] Coven, E.; Paul, M.: Math. systems theory. 8, 167 (1974)
[12] Halmos, P.: Bull. amer. Math. soc.. 49, 619 (1943)
[13] Dunford, N.; Schwartz, J.: Linear operators I. (1964) · Zbl 0084.10402
[14] Denker, M.: Ergodic theory of compact spaces. (1976) · Zbl 0328.28008
[15] Coven, E.; Paul, M.: Israel J. Math.. 20, 165 (1975)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.