Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-19T04:20:48.157Z Has data issue: false hasContentIssue false

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
Affiliation:
Aix Marseille Université, CNRS, Centrale Marseille, I2M UMR 7373, 13453, Marseille, France email benjamin.hellouin@gmail.com, mathieu.sablik@univ-amu.fr
MATHIEU SABLIK
Affiliation:
Aix Marseille Université, CNRS, Centrale Marseille, I2M UMR 7373, 13453, Marseille, France email benjamin.hellouin@gmail.com, mathieu.sablik@univ-amu.fr
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Original Article
Copyright
© Cambridge University Press, 2016