Textbook in PDF format

This unique comprehensive compendium provides extensive studies on reversible cellular automata (RCAs), exhibiting a wide range of interesting phenomena similar to the Game-of-Life, a well-known irreversible CA. The useful reference text also introduces innovative approaches to constructing universal computers in a reversible cellular space. Numerous figures are included to illustrate the evolution of RCA configurations, and to elucidate theoretical results on RCAs. Additionally, readers can observe evolution processes of various RCAs on the free CA simulator Golly using supplementary files. A cellular automaton (CA) is an abstract spatiotemporal model of dynamical systems. In this book, we use a 2-dimensional reversible cellular automaton (RCA) as a model of a reversible world. Although it is an artificial universe, it is useful for studying which kinds of phenomena emerge from a simple reversible law. Here, we use the framework of partitioned cellular automata (PCA), in which each cell is divided into several parts and changes its state depending on the neighboring cells’ parts. By this, we can design reversible CAs very easily. Most puzzles are solved by giving configurations of reversible PCAs, which are the states of the whole cellular space. However, in some cases, configurations given as solutions are very complex, and need millions of cells. Such a case occurs, e.g., when composing configurations that simulate universal computers. To verify the correctness of these solutions, a good simulator for CAs is absolutely necessary besides a theoretical method. Here, we use Golly (golly.sourceforge.io), a general purpose CA simulator, which can simulate evolving processes of very large configurations for a huge number (say, millions or even billions) of steps. Solutions for many puzzle problems are given as rule files and pattern files that are executable on Golly. There is no prerequisite knowledge to read this book, because the framework of the CAs is very simple. Since there are many (i.e., about 370) figures, it may be good to look at only them at first. By this, readers can feel the atmosphere of the whole volume. Though it is better to have some basic knowledge on automata theory to understand several particular sections precisely, it is not required to do so to grasp the main objective of the book. Instead, I strongly recommend the readers to use the simulator Golly, and see fantastic evolving processes of various reversible CAs. Readership: Researchers, professionals, academics, and graduate students in theoretical Computer Science, complex systems and computer engineering