Abstract
This work is a thoughtful extension of the ideas sketched in Montalva et al. (AUTOMATA 2017 exploratory papers proceedings, 2017), aiming at classifying elementary cellular automata (ECA) according to their maximal one-step sensitivity to changes in the schedule of cells update. It provides a complete classification of the ECA rule space for all period sizes \(n > 9\) and, together with the classification for all period sizes \(n \le 9\) presented in Montalva et al. (Chaos Solitons Fractals 113:209–220, 2018), closes this problem and opens further questionings. Most of the 256 ECA rule’s sensitivity is proved or disproved to be maximum thanks to an automatic application of basic methods. We formalize meticulous case disjunctions that lead to the results, and patch failing cases for some rules with simple arguments. This gives new insights on the dynamics of ECA rules depending on the proof method employed, as for the last rules 45 and 105 requiring \(({\texttt{0011}})^*\) induction patterns.
Similar content being viewed by others
Notes
it turns out that this point is important to prove the max-sensitivity of some rules.
References
Aracena J, Demongeot J, Fanchon E, Montalva M (2013) On the number of update digraphs and its relation with the feedback arc sets and tournaments. Discrete Appl Math 161(10):1345–1355
Aracena J, Fanchon E, Montalva M, Noual M (2011) Combinatorics on update digraphs in boolean networks. Discrete Appl Math 159(6):401–409
Aracena J, Goles E, Moreira A, Salinas L (2009) On the robustness of update schedules in boolean networks. Biosystems 97:1–8
Cook M (2004) Universality in elementary cellular automata. Complex Syst 15(1):1–40
de Oliveira PPB (2014) On density determination with cellular automata: results, constructions and directions. J Cell Autom 9(5–6):357–385
Fatès N (2011) Stochastic cellular automata solve the density classification problem with an arbitrary precision. In: STACS’2011, vol 9 of Leibniz international proceedings in informatics (LIPIcs), pp 284–295
Fatès N (2014) A guided tour of asynchronous cellular automata. J Cell Automata 9(5–6):387–416
Gardner M (1970) Mathematical games: the fantastic combinations of John Conway’s new solitaire game “Life”. Sci Am 223(4):120–123
Kari J (2005) Theory of cellular automata: a survey. Theor Comput Sci 334(1–3):3–33
Montalva M, Perrot K, de Oliveira PPB, Ruivo E (2017) Sensitivity to synchronism in some boolean automata networks. In: AUTOMATA 2017 exploratory papers proceedings, pp 69–76
Montalva M, Perrot K, de Oliveira PPB, Ruivo E (2018) Characterisation of the elementary cellular automata in terms of their maximum sensitivity to all possible asynchronous updates. Chaos Solitons Fractals 113:209–220
Noual M (2012) Mises à jour de réseaux d’automates. Ph.D. thesis, Ecole normale supérieure de lyon, Laboratoire de l’Informatique du Parallélisme
Wolfram S (2002) A new kind of science. Wolfram Media
Acknowledgements
This work was partially supported by FONDECYT Iniciación 11150827; CNPq; ECOS-CONICYT C16E01; PACA project FRI-2015 01134; PEPS JCJC INS2I project CGETA; Young Researcher project ANR-18-CE40-0002-01 “FANs”; STIC-AmSud CoDANet project: 19-STIC-03 Campus France 43478PD and CAPES 88881.197456/2018-01; CAPES PrInt project 88887.310281/2018-00; and MackPesquisa Edital 2018.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Perrot, K., Montalva-Medel, M., de Oliveira, P.P.B. et al. Maximum sensitivity to update schedules of elementary cellular automata over periodic configurations. Nat Comput 19, 51–90 (2020). https://doi.org/10.1007/s11047-019-09743-9
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11047-019-09743-9