A1 Refereed original research article in a scientific journal
Reversible Cellular Automata: From Fundamental Classical Results to Recent Developments
Authors: Kari Jarkko
Publisher: Springer Tokyo
Publication year: 2018
Journal: New Generation Computing
Journal name in source: New Generation Computing
Volume: 36
Issue: 3
First page : 145
Last page: 172
Number of pages: 28
ISSN: 0288-3635
eISSN: 1882-7055
DOI: https://doi.org/10.1007/s00354-018-0034-6
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.