Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-26T00:53:13.505Z Has data issue: false hasContentIssue false
  • English
  • Français

Characterization of sets of limit measures of a cellular automaton iterated on a random configuration

Published online by Cambridge University Press:  09 September 2016

BENJAMIN HELLOUIN DE MENIBUS  and
MATHIEU SABLIK
BENJAMIN HELLOUIN DE MENIBUS
Affiliation:
Aix Marseille Université, CNRS, Centrale Marseille, I2M UMR 7373, 13453, Marseille, France email [email protected], [email protected]
MATHIEU SABLIK
Affiliation:
Aix Marseille Université, CNRS, Centrale Marseille, I2M UMR 7373, 13453, Marseille, France email [email protected], [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

The asymptotic behaviour of a cellular automaton iterated on a random configuration is well described by its limit probability measure(s). In this paper, we characterize measures and sets of measures that can be reached as limit points after iterating a cellular automaton on a simple initial measure. In addition to classical topological constraints, we exhibit necessary computational obstructions. With an additional hypothesis of connectivity, we show these computability conditions are sufficient by constructing a cellular automaton realizing these sets, using auxiliary states in order to perform computations. Adapting this construction, we obtain a similar characterization for the Cesàro mean convergence, a Rice theorem on the sets of limit points, and we are able to perform computation on the set of measures, i.e. the cellular automaton converges towards a set of limit points that depends on the initial measure. Last, under non-surjective hypotheses, it is possible to remove auxiliary states from the construction.

Type
Original Article
Information
Ergodic Theory and Dynamical Systems , Volume 38 , Issue 2 , April 2018 , pp. 601 - 650
Copyright
© Cambridge University Press, 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Amoroso, S. and Patt, Y. N.. Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures. J. Comput. Syst. Sci. 6(5) (1972), 448–464.Google Scholar
Aubrun, N. and Sablik, M.. Simulation of effective subshifts by two-dimensional subshift of finite type. Acta Appl. Math. 128(1) (2013), 35–63.CrossRefGoogle Scholar
Boyer, L., Delacourt, M. and Sablik, M.. Construction of 𝜇-limit sets. Proc. 2nd Symp. on Cellular Automata “Journées Automates Cellulaires”, JAC 2010, Turku, Finland, 15–17 December, 2010. Ed. Kari, J.. Turku Center for Computer Science, Turku, 2010, pp. 76–87.Google Scholar
Boyle, M. and Petersen, K.. Hidden Markov processes in the context of symbolic dynamics. Entropy of Hidden Markov Processes and Connections to Dynamical Systems (London Mathematical Society Lecture Note Series 385) . Cambridge University Press, Cambridge, 2011, pp. 5–71.CrossRefGoogle Scholar
Boyer, L., Poupet, V. and Theyssier, G.. On the complexity of limit sets of cellular automata associated with probability measures. Mathematical Foundations of Computer Science 2006 (Proc. 31st Int. Symp., MFCS 2006, Stará Lesná, Slovakia, 28 August–1 September, 2006). 2006, pp. 190–201.Google Scholar
Delacourt, M.. Rice’s theorem for 𝜇-limit sets of cellular automata. Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP ’11) (Lecture Notes in Computer Science, 6756) . Springer, Berlin, 2011, pp. 89–100.Google Scholar
de Menibus, B. H. and Sablik, M.. Self-organisation in cellular automata: a particle-based approach. Developments in Language Theory (Lecture Notes in Computer Science, 6795) . Eds. Mauri, G. and Leporati, A.. Springer, Berlin, 2011, pp. 251–263.Google Scholar
de Menibus, B. H.. Asymptotic behaviour of cellular automata: computation and randomness. PhD Thesis, University of Aix-Marseille, 2014.Google Scholar
Delacourt, M., Poupet, V., Sablik, M. and Theyssier, G.. Directional dynamics along arbitrary curves in cellular automata. Theoret. Comput. Sci. 412(30) (2011), 3800–3821.Google Scholar
Fisch, R.. The one-dimensional cyclic cellular automaton: a system with deterministic dynamics that emulates an interacting particle system with stochastic dynamics. J. Theoret. Probab. 3(2) (1990), 311–338.Google Scholar
Ferenczi, S. and Monteil, T.. Infinite words with uniform frequencies, and invariant measures. Combinatorics, Automata and Number Theory. Eds. Berthé, V. and Rigo, M.. Cambridge University Press, Cambridge, 2010, pp. 374–415.Google Scholar
Ferrari, P. A., Maass, A., Martínez, S. and Ney, P.. Cesàro mean distribution of group automata starting from measures with summable decay. Ergod. Th. & Dynam. Sys. 20(6) (2000), 1657–1670.Google Scholar
Gács, P.. Reliable cellular automata with self-organisation. J. Stat. Phys. 103(1–2) (2001), 45–267.Google Scholar
Galatolo, S., Hoyrup, M. and Rojas, C.. Dynamics and abstract computability: computing invariant measures. Discrete Contin. Dyn. Syst. Ser. A 29(1) (2011), 193–212.Google Scholar
Guillon, P. and Richard, G.. Revisiting the Rice theorem of cellular automata. 27th International Symposium on Theoretical Aspects of Computer Science (STACS ’10). Ed. Marion, J.-Y.. Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2010, pp. 441–452.Google Scholar
Hedlund, G. A.. Endomorphisms and automorphisms of the shift dynamical system. Math. Syst. Theory 3(4) (1969), 320–375.Google Scholar
Hochman, M. and Meyerovitch, T.. A characterisation of the entropies of multidimensional shifts of finite type. Ann. of Math. (2) 171(3) (2010), 2011–2038.CrossRefGoogle Scholar
Hochman, M.. On the dynamics and recursive properties of multidimensional symbolic systems. Invent. Math. 176(1) (2009), 131–167.Google Scholar
Kůrka, P. and Maass, A.. Limit sets of cellular automata associated to probability measures. J. Stat. Phys. 100(5–6) (2000), 1031–1047.Google Scholar
Kůrka, P.. On the measure attractor of a cellular automaton. Discrete Contin. Dyn. Syst. (2005), 524–535.Google Scholar
Lind, D. A.. Applications of ergodic theory and sofic systems to cellular automata. Physica D 10(1–2) (1984), 36–44.Google Scholar
Mazoyer, J.. On optimal solutions to the firing squad synchronisation problem. Theoret. Comput. Sci. 168(2) (1996), 367–404.Google Scholar
Meyerovitch, T.. Growth-type invariants for ℤ d subshifts of finite type and arithmetical classes of real numbers. Invent. Math. 184 (2011), 567–589.Google Scholar
Maass, A. and Martínez, S.. On Cesàro limit distribution of a class of permutative cellular automata. J. Stat. Phys. 90(1–2) (1998), 435–452.Google Scholar
Petersen, K.. Ergodic Theory (Cambridge Studies in Advanced Mathematics, 2) . Cambridge University Press, Cambridge, 1983.Google Scholar
Pivato, M. and Yassawi, R.. Limit measures for affine cellular automata. Ergod. Th. & Dynam. Sys. 22(4) (2002), 1269–1287.Google Scholar
Shields, P. C.. The Ergodic Theory of Discrete Sample Paths (Graduate Studies in Mathematics, 13) . American Mathematical Society, Providence, RI, 1996.Google Scholar
Weihrauch, K.. An introduction. Computable Analysis (Texts in Theoretical Computer Science. An EATCS Series) . Springer, Berlin, 2000.CrossRefGoogle Scholar
Young, L.-S.. What are SRB measures, and which dynamical systems have them? J. Statist. Phys. 108(5–6) (2002), 733–754.Google Scholar
Ziegler, M.. Computability and continuity on the real arithmetic hierarchy and the power of type-2 nondeterminism. New Computational Paradigms (Lecture Notes in Computer Science, 3526) . Eds. Cooper, S. B., Löwe, B. and Torenvliet, L.. Springer, Berlin, 2005, pp. 562–571.Google Scholar
Zheng, X. and Weihrauch, K.. The arithmetical hierarchy of real numbers. MLQ Math. Log. Q. 47(1) (2001), 51–65.Google Scholar