Abstract
We construct a one-dimensional reversible cellular automaton that is computationally universal in a rather strong sense while being highly non-sensitive to initial conditions as a dynamical system. The cellular automaton has no sensitive subsystems. The construction is based on a simulation of a reversible Turing machine, where a bouncing signal activates the Turing machine to make single steps whenever the signal passes over the machine.
Research supported by the Academy of Finland Grant 131558.
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
Banks, J., Brooks, J., Cairns, G., Davis, G., Stacey, P.: On devaney’s definition of chaos. Am. Math. Mon. 99(4), 332–334 (1992)
Bennett, C.H.: Logical reversibility of computation. IBM J. Res. Dev. 17(6), 525–532 (1973)
Delvenne, J.C., Kurka, P., Blondel, V.D.: Decidability and universality in symbolic dynamical systems. Fundam. Inform. 74(4), 463–490 (2006)
Devaney, R.: An introduction to chaotic dynamical systems. Global analysis, pure and applied, Benjamin/Cummings (1986)
Kari, J., Ollinger, N.: Periodicity and immortality in reversible computing. In: Ochmański, E., Tyszkiewicz, J. (eds.) MFCS 2008. LNCS, vol. 5162, pp. 419–430. Springer, Heidelberg (2008)
Kari, J., Salo, V., Törmä, I.: Trace complexity of chaotic reversible cellular automata. In: Yamashita, S., Minato, S. (eds.) RC 2014. LNCS, vol. 8507, pp. 54–66. Springer, Heidelberg (2014)
Langton, C.G.: Computation at the edge of chaos: Phase transitions and emergent computation. Phys. D 42(1–3), 12–37 (1990)
Morita, K., Shirasaki, A., Gono, Y.: A 1-tape 2-symbol reversible turing machine. Trans. IEICE Japan E72, 223–228 (1989)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Kari, J. (2015). A Universal Cellular Automaton Without Sensitive Subsystems. In: Isokawa, T., Imai, K., Matsui, N., Peper, F., Umeo, H. (eds) Cellular Automata and Discrete Complex Systems. AUTOMATA 2014. Lecture Notes in Computer Science(), vol 8996. Springer, Cham. https://doi.org/10.1007/978-3-319-18812-6_4
Download citation
DOI: https://doi.org/10.1007/978-3-319-18812-6_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-18811-9
Online ISBN: 978-3-319-18812-6
eBook Packages: Computer ScienceComputer Science (R0)