Reversible Cellular Automata: From Fundamental Classical Results to Recent Developments | New Generation Computing Skip to main content
Springer Nature Link
Log in

Reversible Cellular Automata: From Fundamental Classical Results to Recent Developments

  • Research Paper
  • Published:
New Generation Computing Aims and scope Submit manuscript

Abstract

A cellular automaton is a dynamical system on an infinite array of cells defined by a local update rule that is applied simultaneously at all cells. By carefully choosing the update rule, the global dynamics can be made information preserving. In this case, the cellular automaton is called reversible. In this article, we explain fundamental classical results concerning reversible cellular automata and discuss some more recent developments on selected topics. Classical results reviewed include the Curtis–Hedlund–Lyndon theorem, the Garden-of-Eden theorem and the invariance of uniform Bernoulli distribution under reversible cellular automata. We then describe several techniques to construct reversible cellular automata and a method to determine whether a given one-dimensional automaton is reversible. We present undecidability issues concerning reversible cellular automata and discuss three types of universality: computational universality, intrinsic universality, and physical universality. We finish with short notes about time symmetry, expansiveness, and conservation laws.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Kari, J.: Reversible cellular automata. Developments in language theory. Lecture Notes in Computer Science, vol. 3572, pp. 57–68. Springer, Berlin (2005)

  2. Kari, J.: Theory of cellular automata: a survey. Theoret. Comput. Sci. 334(1–3), 3–33 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  3. Morita, K.: Reversible computing and cellular automata–a survey. Theoret. Comput. Sci. 395(1), 101–131 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  4. Morita, K.: Theory of Reversible Computing, Monographs in Theoretical Computer Science, An EATCS Series. Springer, New York (2017)

    Google Scholar 

  5. Hedlund, G.A.: Endomorphisms and automorphisms of the shift dynamical systems. Math. Syst. Theory 3(4), 320–375 (1969)

    Article  MathSciNet  MATH  Google Scholar 

  6. Richardson, D.: Tessellations with local transformations. J. Comput. Syst. Sci. 6(5), 373–388 (1972)

    Article  MathSciNet  MATH  Google Scholar 

  7. Moore, E.F.: Machine models of self-reproduction. Proc. Symp. Appl. Math. 14, 17–33 (1963)

    Article  Google Scholar 

  8. Myhill, J.: The converse to Moore’s garden-of-eden theorem. Proc. Am. Math. Soc. 14, 685–686 (1963)

    MathSciNet  MATH  Google Scholar 

  9. Berlekamp, E., Conway, J., Guy, R.: Winning Ways, for Your Mathematical Plays: Games in Particular. vol. 2. Academic (1982)

  10. Gardner, M.: Mathematical games: The fantastic combinations of John Conway’s new solitaire game “life”. Scientific American 223, 120–123 (1970)

  11. Ceccherini-Silberstein, T., Coornaert, M.: Cellular Automata and Groups. Springer Monographs in Mathematics. Springer, Berlin (2010)

    Book  MATH  Google Scholar 

  12. Gottschalk, W.: Some general dynamical notions. In: Recent Advances in Topological Dynamics, Lecture Notes in Mathematics, vol. 318, pp. 120–125. Springer, New York (1973)

  13. Kari, J.: Universal pattern generation by cellular automata. Theoret. Comput. Sci. 429, 180–184 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  14. Morita, K., Harao, M.: Computation universality of one-dimensional reversible (injective) cellular automata. IEICE Trans. E 72(6), 758–762 (1989)

    Google Scholar 

  15. Kari, J.: Representation of reversible cellular automata with block permutations. Math. Syst. Theory 29(1), 47–61 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  16. Kari, J.: On the circuit depth of structurally reversible cellular automata. Fundamenta Informaticae 38(1–2), 93–107 (1999)

    MathSciNet  MATH  Google Scholar 

  17. Toffoli, T., Margolus, N.: Invertible cellular automata: a review. Phys. D 45, 229–253 (1990)

  18. Margolus, N.: Physics-like models of computation. Phys. D Nonlinear Phenom. 10(1), 81–95 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  19. Hardy, J., Pomeau, Y., de Pazzis, O.: Time evolution of a two-dimensional classical lattice system. Phys. Rev. Lett. 31, 276–279 (1973)

    Article  Google Scholar 

  20. Vichniac, G.Y.: Simulating physics with cellular automata. Phys. D Nonlinear Phenom. 10(1–2), 96–116 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  21. Amoroso, S., Patt, Y.N.: Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures. J. Comput. Syst. Sci. 6(5), 448–464 (1972)

    Article  MathSciNet  MATH  Google Scholar 

  22. Kari, J.: Reversibility of 2D cellular automata is undecidable. Phys. D Nonlinear Phenom. 45(1), 379–385 (1990)

    Article  MATH  Google Scholar 

  23. Kari, J.: Reversibility and surjectivity problems of cellular automata. J. Comput. Syst. Sci. 48(1), 149–182 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  24. Sutner, K.: De Bruijn graphs and linear cellular automata. Complex Syst. 5(1), 19–30 (1991)

    MathSciNet  MATH  Google Scholar 

  25. Czeizler, E., Kari, J.: A tight linear bound on the neighborhood of inverse cellular automata. In: Automata, Languages and Programming, 32nd International Colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005, Proceedings, pp. 410–420 (2005)

  26. Kari, J.: Snakes and cellular automata: Reductions and inseparability results. In: Kulikov, A., Vereshchagin, N. (eds.) Computer Science—Theory and Applications, pp. 223–232. Springer, Berlin (2011)

    Google Scholar 

  27. Boyle, M.: Open problems in symbolic dynamics. Geometric and Probabilistic Structures in Dynamics. Contemporary Mathematics, vol. 469, pp. 69–118. American Mathematical Society, Providence (2008)

  28. Kari, J., Ollinger, N.: Periodicity and immortality in reversible computing. In: Ochmański, E., Tyszkiewicz, J. (eds.) Mathematical Foundations of Computer Science 2008, pp. 419–430. Springer, Berlin (2008)

    Chapter  Google Scholar 

  29. Delacourt, M., Ollinger, N.: Permutive one-way cellular automata and the finiteness problem for automaton groups. In: J. Kari, F. Manea, I. Petre (eds.) Unveiling Dynamics and Complexity, pp. 234–245. Springer International Publishing (2017)

  30. Cook, M.: Universality in elementary cellular automata. Complex Syst. 15(1) (2004)

  31. Bennett, C.H.: Logical reversibility of computation. IBM J. Res. Dev. 17(6), 525–532 (1973)

    Article  MathSciNet  MATH  Google Scholar 

  32. Lecerf, Y.: Machines de Turing réversibles. Récursive insolubilité en \(n\in {N}\) de l’équation \(u=\theta ^n u\), où \(\theta\) est un “isomorphisme de code”. Comptes Rendus Hebdomadaires des Séances de l’Académie des Sciences 257, 2597–2600 (1963)

  33. Morita, K.: Universality of a reversible two-counter machine. Theoret. Comput. Sci. 168(2), 303–320 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  34. Toffoli, T.: Computation and construction universality of reversible cellular automata. J. Comput. Syst. Sci. 15(2), 213–231 (1977)

    Article  MathSciNet  MATH  Google Scholar 

  35. Morita, K.: Reversible simulation of one-dimensional irreversible cellular automata. Theoret. Comput. Sci. 148(1), 157–163 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  36. Dubacq, J.C.: How to simulate Turing machines by invertible one-dimensional cellular automata. Int. J. Found. Comput. Sci. 6(4), 395–402 (1995)

    Article  MATH  Google Scholar 

  37. Delorme, M., Mazoyer, J., Ollinger, N., Theyssier, G.: Bulking i: An abstract theory of bulking. Theoretical Computer Science 412(30), 3866–3880 (2011) (Cellular Automata and Discrete Complex Systems)

  38. Delorme, M., Mazoyer, J., Ollinger, N., Theyssier, G.: Bulking ii: Classifications of cellular automata. Theoretical Computer Science 412(30), 3881–3905 (2011) (Cellular Automata and Discrete Complex Systems)

  39. Ollinger, N.: Universalities in cellular automata. In: Rozenberg et al. [54], pp. 189–229

  40. Durand-Lose, J.: Computing inside the billiard ball model. In: Adamatzky, A. (ed.) Collision-Based Computing, pp. 135–160. Springer, London (2002)

    Chapter  Google Scholar 

  41. Fredkin, E., Toffoli, T.: Conservative logic. Int. J. Theoret. Phys. 21(3), 219–253 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  42. Durand-Lose, J.O.: Intrinsic universality of a 1-dimensional reversible cellular automaton. In: R. Reischuk, M. Morvan (eds.) STACS 97, 14th Annual Symposium on Theoretical Aspects of Computer Science, Lübeck, Germany, February 27 - March 1, 1997, Proceedings Lecture Notes in Computer Science, vol. 1200, pp. 439–450. Springer (1997)

  43. Janzing, D.: Is there a physically universal cellular automaton or hamiltonian? (2010)

  44. Schaeffer, L.: A physically universal cellular automaton. In: Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS ’15, pp. 237–246. ACM, New York (2015)

  45. Salo, V., Törmä, I.: A one-dimensional physically universal cellular automaton. In: J. Kari, F. Manea, I. Petre (eds.) Unveiling Dynamics and Complexity, pp. 375–386. Springer International Publishing (2017)

  46. Moreira, A., Gajardo, A.: Time-symmetric cellular automata. In: J. Kari (ed.) Proceedings of JAC 2010, Journées Automates Cellulaires, pp. 180–190. TUCS, Turku Centre for Computer Science (2010)

  47. Gajardo, A., Kari, J., Moreira, A.: On time-symmetry in cellular automata. J. Comput. Syst. Sci. 78(4), 1115–1126 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  48. Shereshevsky, M.A.: Expansiveness, entropy and polynomial growth for groups acting on subshifts by automorphisms. Indagationes Mathematicae 4(2), 203–210 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  49. Hattori, T., Takesue, S.: Additive conserved quantities in discrete-time lattice dynamical systems. Phys. D Nonlinear Phenom. 49(3), 295–322 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  50. Formenti, E., Kari, J., Taati, S.: On the hierarchy of conservation laws in a cellular automaton. Nat. Comput. 10(4), 1275–1294 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  51. Kari, J., Taati, S.: Statistical mechanics of surjective cellular automata. J. Stat. Phys. 160(5), 1198–1243 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  52. Kari, J., Taati, S.: Conservation laws and invariant measures in surjective cellular automata. In: N. Fatès, E.G. Chacc, A. Maass, I. Rapaport (eds.) AUTOMATA, Discrete Mathematics and Theoretical Computer Science Proceedings, vol. AP, pp. 113–122. DMTCS (2011)

  53. Kari, J.: Basic concepts of cellular automata. In: Rozenberg, G., Bäck, T., Kok, J.N. (eds.) Handbook of Natural Computing, vol. 1, pp. 3–24. Springer, New York (2010)

  54. Kůrka, P.: Topological and Symbolic Dynamics. Collection SMF, Société mathématique de France (2003)

  55. Toffoli, T., Margolus, N.: Cellular Automata Machines: A New Environment for Modeling. MIT press (1987)

  56. Chopard, B., Droz, M.: Cellular Automata Modeling of Physical Systems. Cambridge University Press, Cambridge (1998)

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics and Statistics, University of Turku, 20014, Turku, Finland

    Jarkko Kari

Authors
  1. Jarkko Kari
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jarkko Kari.

Additional information

Research supported by the Academy of Finland Grant 296018.

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Kari, J. Reversible Cellular Automata: From Fundamental Classical Results to Recent Developments. New Gener. Comput. 36, 145–172 (2018). https://doi.org/10.1007/s00354-018-0034-6

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00354-018-0034-6

Keywords

Search

Navigation