Theory of reversible computing (Q1684627)

Deterministic algorithms, such as deterministic finite automata or deterministic Turing machines, have an extensive theory, which is an important component of the theory of algorithms and computation. Actually, at the beginning of the theory of algorithms when researchers were only trying to build a formal definition of an algorithm, one of the basic suppositions of the notion of algorithm was determinism of computation controlled by the algorithm (cf., for example, [\textit{H. Rogers jun.}, Theory of recursive functions and effective computability. Maidenhead, Berksh.: McGraw-Hill Publishing Company, Ltd. (1967; Zbl 0183.01401)]). The dual concept to the concept of deterministic computation is reversible computation, which was introduced and studied much later than deterministic computation. In this case, duality means that while in deterministic computation, each step allows not more than one continuation, i.e., the next step is always unique if it exists, in reversible computation, each step has only one predecessor. The idea of reversibility comes from physics where contemporary theories of quantum reality imply that on the quantum level, almost all processes are reversible. The practical goal of computational reversibility is to decrease consumption of energy in computing. In reversible automata, there is no energy dissipation within the computation process. That is why computer scientists and physicists started investigating reversible computing with the pioneering paper of \textit{C. H. Bennett} [IBM J. Res. Dev. 17, 525--532 (1973; Zbl 0267.68024)]. Since that time, many authors have published papers on reversible computing and now we have a fundamental treatise on the theory of reversible computing written by one of the leading experts in this area. The book under review has several advantages in representation of reversible computing. First, exposition is developed in a rigorous theoretical setting of mathematical models of algorithms and automata. Second, the book has a high-quality and clear-cut architecture when exposition goes from the lowest level of reversible logic elements through reversible functional modules and composed logic elements to the high level of reversible abstract automata. The highest level consists of two parts -- reversible abstract automata that perform centralized computations, such as reversible Turing machines and reversible counter machines, and reversible abstract automata that perform distributed computations, such as reversible cellular automata. Third, the book includes a chapter on self-reproducing reversible automata. This is an important topic, which is rarely discussed in contemporary books on theoretical computer science. It is also important that the author thoroughly explains how reversibility can be effectively utilized in computing, for example, providing reduction of energy dissipation. It is also possible to suggest that reversibility can make testing and fault detection in software and hardware systems easier. It is understandable that it might be unreasonable and even impossible to include all results and accomplishments of the theory of reversible computing. It is the competence of the author to select topics to include in the book. However, one topic absent in the book definitely deserves representation. Namely, reversible quantum computing, which originated as a theoretical discipline in the works of the prominent physicist Paul Benioff, who in 1980 introduced and studied reversible quantum Turing machines [\textit{P. Benioff}, ``The computer as a physical system: a microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines'', J. Stat. Phys. 22, No. 5, 563--591 (1980; Zbl 1382.68066)]. It is necessary to remark that this paper was the first publication in the theory of quantum computing. In his book, the author studies only subrecursive reversible algorithms and automata, such as reversible logic elements and reversible circuits, and recursive reversible algorithms and automata, such as reversible Turing machines and reversible cellular automata. Recursive automata and algorithms are considered as the top level in computing. However, to adequately model and effectively develop contemporary information technology, it is necessary to go to the higher level studying and utilizing superrecursive algorithms and automata, such as inductive Turing machines [the reviewer, Super-recursive algorithms. New York, NY: Springer (2005; Zbl 1070.68038)] and inductive cellular automata [the reviewer, ``Inductive cellular automata'', Int. J. Data Struct. Algorithms 1, No. 1, 1--9 (2015)]. Thus, it would be interesting and important to explore superrecursive reversible algorithms and automata, such as reversible inductive Turing machines and reversible inductive cellular automata.