Abstract
Lyapunov exponents are an important concept in differentiable dynamical systems and they measure stability or sensitivity in the system. Their analogues for cellular automata were proposed by Shereshevsky and since then they have been further developed and studied. In this paper we focus on a conjecture claiming that there does not exist such a sensitive cellular automaton, that would have both the right and the left pointwise Lyapunov exponents taking the value zero, for each configuration. In this paper we prove this conjecture false by constructing such a cellular automaton, using aperiodic, complete Turing machines as a building block.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Blondel, V.D., Cassaigne, J., Nichitiu, C.M.: On the presence of periodic configurations in Turing machines and in counter machines. Theor. Comput. Sci. 289, 573–590 (2002)
Bressaud, X., Tisseur, P.: On a zero speed sensitive cellular automaton. Nonlinearity 20(1), 1–19 (2006). https://doi.org/10.1088/0951-7715/20/1/002
Cassaigne, J., Ollinger, N., Torres, R.: A small minimal aperiodic reversible Turing machine. J. Comput. Syst. Sci. 84 (2014). https://doi.org/10.1016/j.jcss.2016.10.004
D’amico, M., Manzini, G., Margara, L.: On computing the entropy of cellular automata. In: Larsen, K.G., Skyum, S., Winskel, G. (eds.) ICALP 1998. LNCS, vol. 1443, pp. 470–481. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0055076
Finelli, M., Manzini, G., Margara, L.: Lyapunov exponents vs expansivity and sensitivity in cellular automata. In: Bandini, S., Mauri, G. (eds.) ACRI 1996, pp. 57–71. Springer, London (1997). https://doi.org/10.1007/978-1-4471-0941-9_6
Greiner, W.: Lyapunov exponents and chaos. In: Greiner, W. (ed.) Classical Mechanics, pp. 503–516. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-03434-3_26
Guillon, P., Salo, V.: Distortion in one-head machines and cellular automata. In: Dennunzio, A., Formenti, E., Manzoni, L., Porreca, A.E. (eds.) Cellular Automata and Discrete Complex Systems, pp. 120–138. Springer International Publishing, Cham (2017). https://doi.org/10.1007/978-3-319-58631-1_10
Jeandel, E.: Computability of the entropy of one-tape Turing machines. Leibniz International Proceedings in Informatics, LIPIcs 25 (2013). https://doi.org/10.4230/LIPIcs.STACS.2014.421
Kůrka, P.: Topological dynamics of cellular automata. In: Meyers, R.A. (ed.) Encyclopedia of Complexity and Systems Science, pp. 9246–9268. Springer, New York (2009). https://doi.org/10.1007/978-0-387-30440-3_556
Kůrka, P.: On topological dynamics of Turing machines. Theor. Comput. Sci. 174(1), 203–216 (1997). https://doi.org/10.1016/S0304-3975(96)00025-4. http://www.sciencedirect.com/science/article/pii/S0304397596000254
Lyapunov, A.: General Problem of the Stability of Motion. Control Theory and Applications Series. Taylor & Francis (1992). https://books.google.fi/books?id=4tmAvU3_SCoC
Shereshevsky, M.A.: Lyapunov exponents for one-dimensional cellular automata. J. Nonlinear Sci. 2(1), 1–8 (1992). https://doi.org/10.1007/BF02429850
Tisseur, P.: Cellular automata and Lyapunov exponents. Nonlinearity 13(5), 1547–1560 (2000). https://doi.org/10.1088/0951-7715/13/5/308
Wolfram, S.: Universality and complexity in cellular automata. Phys. D Nonlinear Phenom. 10(1), 1–35 (1984). https://doi.org/10.1016/0167-2789(84)90245-8. http://www.sciencedirect.com/science/article/pii/0167278984902458
Wolfram, S.: Twenty problems in the theory of cellular automata. Phys. Scr. T9, 170–183 (1985). https://doi.org/10.1088/0031-8949/1985/t9/029
Acknowledgements
The author acknowledges the emmy.network foundation under the aegis of the Fondation de Luxembourg for its financial support.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 IFIP International Federation for Information Processing
About this paper
Cite this paper
Hotanen, T. (2020). Everywhere Zero Pointwise Lyapunov Exponents for Sensitive Cellular Automata. In: Zenil, H. (eds) Cellular Automata and Discrete Complex Systems. AUTOMATA 2020. Lecture Notes in Computer Science(), vol 12286. Springer, Cham. https://doi.org/10.1007/978-3-030-61588-8_6
Download citation
DOI: https://doi.org/10.1007/978-3-030-61588-8_6
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-61587-1
Online ISBN: 978-3-030-61588-8
eBook Packages: Computer ScienceComputer Science (R0)