main-content

This book is a tribute to Kenichi Morita’s ideas and achievements in theoretical computer science, reversibility and computationally universal mathematical machines. It offers a unique source of information on universality and reversibility in computation and is an indispensable book for computer scientists, mathematicians, physicists and engineers.

Morita is renowned for his works on two-dimensional language accepting automata, complexity of Turing machines, universality of cellular automata, regular and context-free array grammars, and undecidability. His high-impact works include findings on parallel generation and parsing of array languages by means of reversible automata, construction of a reversible automaton from Fredkin gates, solving a firing squad synchronization problem in reversible cellular automata, self-reproduction in reversible cellular spaces, universal reversible two-counter machines, solution of nondeterministic polynomial (NP) problems in hyperbolic cellular automata, reversible P-systems, a new universal reversible logic element with memory, and reversibility in asynchronous cellular automata.

Kenichi Morita’s achievements in reversibility, universality and theory of computation are celebrated in over twenty high-profile contributions from his colleagues, collaborators, students and friends. The theoretical constructs presented in this book are amazing in their diversity and depth of intellectual insight, addressing: queue automata, hyperbolic cellular automata, Abelian invertible automata, number-conserving cellular automata, Brownian circuits, chemical automata, logical gates implemented via glider collisions, computation in swarm networks, picture arrays, universal reversible counter machines, input-position-restricted models of language acceptors, descriptional complexity and persistence of cellular automata, partitioned cellular automata, firing squad synchronization algorithms, reversible asynchronous automata, reversible simulations of ranking trees, Shor’s factorization algorithms, and power consumption of cellular automata.

A Snapshot of My Life

Abstract
I was born on 30 March 1949 in Osaka as a son of my father Masukichi and my mother Fusako. My parents influenced me largely, since I had neither brother nor sister. My father was an electrical engineer, and thus I also liked making or designing various functional things. My later research style may be affected by such an activity. When I was a high school student, I started to make electrical and electronic circuits as a hobby. As many hobbyists in those days did, I first assembled a radio from vacuum tubes and some other components. I also composed digital circuits, such as logic gates and flip-flops, out of transistors, diodes, resistors and capacitors. Around the end of 1960’s, TTL (transistor-transistor logic) ICs became available. So, I made several logic circuits for digital apparatus, for example a digital clock, using ICs also as a hobby. At that time, I dreamed to assemble a small digital computer out of TTL ICs, but, of course, it was not possible for me.
Kenichi Morita

FSSP Algorithms for 2D Rectangular Arrays. Recent Developments

Abstract
Synchronization of large-scale networks is an important and fundamental computing primitive in parallel and distributed systems. The synchronization in cellular automata, known as the Firing Squad Synchronization Problem (FSSP), has been studied extensively for more than fifty years, and a rich variety of synchronization algorithms has been proposed. In this article, we give a survey on a class of minimum-time FSSP algorithms for two-dimensional (2D) rectangular arrays. The algorithms discussed here are all based on an L-shaped mapping, where the synchronized configurations on 1D arrays are mapped efficiently onto a 2D array in an L-shaped form, yielding a 2D minimum-time FSSP algorithm.
Hiroshi Umeo

Abelian Invertible Automata

Abstract
Invertible transducers are particular Mealy automata that define so-called automata groups, subgroups of the full automorphism group of the infinite binary tree. In the recent past, automata groups have become a major source of interesting and challenging constructions in group theory. While this research typically focuses on properties of the associated groups, we describe the topological structure of the associated automata in the special case where the group in question is free Abelian. As it turns out, there are connections between these automata and the theory of algebraic number fields as well as the theory of tiles. We conclude with a conjecture about the connectivity properties of the canonical invertible automata generating free Abelian groups.
Klaus Sutner

Simulation and Intrinsic Universality Among Reversible Cellular Automata, the Partition Cellular Automata Leverage

Abstract
This chapter presents the use of Partitioned Cellular Automata—introduced by Morita and colleagues— as the tool to tackle simulation and intrinsic universality in the context of Reversible Cellular Automata. Cellular automata (CA) are mappings over infinite lattices such that all cells are updated synchronously according to the states around each one and a common local function. A CA is reversible if its global function is invertible and its inverse can also be expressed as a CA. Kari proved in 1989 that invertibility is not decidable (for CA of dimension at least 2) and is thus hard to manipulate. Partitioned Cellular Automata (PCA) were introduced as an easy way to handle reversibility by partitioning the states of cells according to the neighborhood. Another approach by Margolus led to the definition of Block CA (BCA) where blocks of cells are updated independently. Both models allow easy check and design for reversibility. After proving that CA, BCA and PCA can simulate each other, it is proven that the reversible sub-classes can also simulate each other contradicting the intuition based on decidability results. In particular, it is proven that any d-dimensional reversible CA (d-R-CA) can be expressed as a BCA with $$d+1$$ partitions. This proves a 1990 conjecture by Toffoli and Margolus (Physica D 45) improved and partially proved by Kari in 1996 (Mathematical System Theory 29). With the use of signals and reversible programming, a 1-R-CA that is intrinsically universal —able to simulate any 1-R-CA— is built. Finally, with a peculiar definition of simulation, it is proven that any CA (reversible or not) can be simulated by a reversible one. All these results extend to any dimension.
Jérôme Durand-Lose

A Weakly Universal Cellular Automaton on the Grid {8, 3} with Two States

Abstract
In this chapter we present a result which improves a previous one established by the author. Here we prove that it is possible to construct a weakly universal cellular automaton on the tessellation $$\{8,3\}$$ with two states only. Note that the cellular automaton lives in the hyperbolic plane, that the proof yields an explicit construction and that the constructed automaton is not rotationally invariant.
Maurice Margenstern

Cellular Automata: Descriptional Complexity and Decidability

Abstract
We give a survey on the descriptional complexity of cellular models including one-way and two-way cellular automata, iterative arrays, and models with a fixed number of cells. For the former models so-called non-recursive trade-offs can be shown, that is, the savings in size that such automata may provide are not bounded by any recursive function. A consequence is that almost all commonly studied decidability questions are undecidable and not even semidecidable for such automata. On the other hand, for the latter models with a fixed number of cells it is possible to show recursive, in particular, polynomial bounds for mutual transformations which yield the decidability of the standard questions. Finally, we summarize results on the state complexity of the Boolean operations for one-way cellular automata and their variant with a fixed number of cells.
Martin Kutrib, Andreas Malcher

Invertible Construction of Decimal-to-Binary Converter Using Reversible Elements

Abstract
We design a logic circuit that is capable of converting from a one-digit decimal number to equivalent four-bit binary number. The circuit is composed by reversible elements each of which takes an equal number of input and output lines, associated with a memory to store a binary state. Reversible elements, as claimed by Morita, (International Conference on Machines, Computations, and Universality, 2001) [8], allow more straightforward and efficient constructions of circuits than conventional reversible logic gates. In particular, the circuit is invertible in the sense that reversing the functionalities of each element in it directly gives rise to another circuit which conducts the inverse conversion.
Tai-Ran He, Jia Lee, Teijiro Isokawa

Power Consumption in Cellular Automata

Abstract
Cellular Automata (CAs) have been established as one of the most intriguing and efficient computational tools of our era with unique properties to fit well with the most of the upcoming nanotechnological and parallel computation aspects. Algorithms based on CAs are ideally suited for hardware implementation, due to their discreteness and their simple, regular and modular structure with local interconnections. On the other hand, power dissipation is considered as a rather limiting parameter for the advancement of high performance hardware design. In this chapter the undergoing relationship between CAs and the corresponding power consumption would be exploited as a matter of importance for their hardware design analysis with many promising aspects. First of all in order to establish a clear connection, a power estimation model for combinational logic circuits using CA and focused on glitching estimation will be presented to elucidate the application of CA model to hardware power dissipation measurements. Following that, the power consumption of CA based logic circuits and namely of 1-d CAs rules logic circuits will be analytically investigated. In particular, CMOS power consumption estimation measurements for all the Wolfram 1-d CAs rules as well as entropy variation measurements were conducted for various study cases and different initial conditions and the findings are discussed in detail and in terms of 1-d CAs rules categorization.
Georgios Ch. Sirakoulis, Ioannis Karafyllidis

Logical Gates via Gliders Collisions

Abstract
An elementary cellular automaton with memory is a chain of finite state machines (cells) updating their state simultaneously and by the same rule. Each cell updates its current state depending on current states of its immediate neighbours and a certain number of its own past states. Some cell-state transition rules support gliders, compact patterns of non-quiescent states translating along the chain. We present designs of logical gates, including reversible Fredkin gate and controlled not gate, implemented via collisions between gliders.
Genaro J. Martínez, Andrew Adamatzky, Kenichi Morita

Computation and Pattern Formation by Swarm Networks with Brownian Motion

Abstract
Swarm Networks are networks of cells of which the functionalities are determined by the presence or absence of connections with cells around them. They have a more flexible neighborhood than Cellular Automata, and can thus be regarded as a generalization of the latter. This chapter describes Swarm Networks in which connections can be changed dynamically, and in which the cells are subject to Brownian motion. According to these characteristics, the model mimics behavior typically encountered in biological organisms. Two types of Swarm Networks are described in this chapter: one has the ability of universal computation through the implementation of a universal Brownian circuit, and the other has the ability of pattern formation in which a circle is formed through the serial connection of agents.
Teijiro Isokawa, Ferdinand Peper

Clean Reversible Simulations of Ranking Binary Trees

Abstract
We propose clean reversible simulations of ranking binary trees and unranking as reversible algorithms for reversible computing systems, which are useful for enumerating and randomly generating binary trees. Algorithms for ranking binary trees and their inverses have been studied since the 1970s. Each of these algorithms can be converted into a reversible simulation by saving all data and control information otherwise lost, and each pair of ranking and unranking reversible programs can be combined to realize a clean reversible simulation by using the Bennett method. However, such a clean reversible simulation requires multiple traversal of the given data and/or intermediate data as well as additional storage proportional to the length of the computation. We show that for Knott’s ranking and unranking algorithms, additional storage usage can be reduced by using the proper assertions of reversible loops in embedded reversible simulations. We also show a clean reversible simulation that involves only one traversal. The running time and memory usage of the proposed clean reversible simulations are asymptotically equivalent to those of the original programs by Knott with intermediate garbage of constant size. In general, the derivation strategy of efficient reversible programs from irreversible ones has not yet been established, and this study can be seen as one of the case studies. All the reversible programs presented in this paper can be run on an interpreter of the reversible programming language Janus.
Yuhi Ohkubo, Tetsuo Yokoyama, Chishun Kanayama

On Radius 1 Nontrivial Reversible and Number-Conserving Cellular Automata

Abstract
Reversibiliity and number-conservation are widely studied physics-like constraints for cellular automata (CA). Although both seem to be ‘natural’ constraints for a CA, it was conjectured that one-dimensional reversible and number-conserving CA (RNCCA) only has a limited computing ability. Particularly in the case of radius 1/2 (2-neighbor), it was shown that the class of RNCCA is equal to a trivial class of CA, so called shift-identity product cellular automata (SIPCA). But recently it was also shown that a RNCCA of neighborhood size four is computation-universal. In this paper, we list radius 1 (3-neighbor) RNCCAs up to 4-state by exhaustive search. In contrast to the radius 1/2 case, there are three new types of nontrivial RNCCA rules in the case of 4-state. We also show that it is possible to compose new nontrivial RNCCAs by modifying a SIPCA even when the state number is larger than four.
Katsunobu Imai, Bruno Martin, Ryohei Saito

The Computing Power of Determinism and Reversibility in Chemical Reaction Automata

Abstract
Chemical reaction automata (CRAs) are computing models with multiset storage based on multiset rewriting introduced in Okubo, Yokomori, (DNA20, LNCS, vol. 8727, pp. 53–66, (2014), [25]). A CRA consists of a finite set of reactions (or pairs of multisets called reactants and products, respectively) and an initial multiset as well as a set of final multisets. Taking an input symbol in the current configuration (multiset) a CRA changes it into a new configuration. Thus, a CRA offers an automaton-like computing model to investigate the computational analysis of chemical reactions. On the other hand, since any (irreversible) Turing machine was proven to be effectively simulated by a reversible Turing machine in Bennett, (IBM J Res Dev, 17(6), 525–532, (1973), [4]), reversible computing has become a research field that has been receiving increased attention. In this paper we introduce the notions of determinism and reversibility into CRAs, and investigate the computational powers of those classes of CRAs in comparison with the language classes of Chomsky hierarchy. The computing power of reversible CRAs involves the physical realization of molecular programming of chemical reaction networks (Thachuk, Condon, DNA 18, LNCS, vol. 7433, pp. 135–149, (2012), [32]) with DNA strand displacement system implementation (Qian, Winfree, Science, 332, 1196–1201, (2011), [29]), and therefore, it is of great significance to elucidate the computing capabilities of both deterministic and reversible CRAs from the theoretical viewpoint of molecular computing.
Fumiya Okubo, Takashi Yokomori

On Non-polar Token-Pass Brownian Circuits

Abstract
Brownian circuits are asynchronous circuits in which signals—represented as tokens—are able to fluctuate along wires. These fluctuations are used as a stochastic search mechanism to drive computations from a state of input to a state of output. Token-Pass circuits are a type of circuits in which wires will not merge or split. Rather, they are linear: each token remains on its wire during computation, and it will interact with other tokens only at points where they pass through circuit elements. The T-element, introduced in [Peper, Lee, Carmona, Cortadella, Morita, “Brownian Circuits: Fundamentals,” 2013], is a circuit element in which three wires pass through, and it was shown to be universal, provided the circuit it is employed in is Brownian. The Brownian circuit designs based on the T-element in the above paper have in common that they implicitly assume a bias in the direction in which tokens flow on average, even though tokens may fluctuate forward and backward during the course of a computation. This chapter proposes a new type of Brownian Token-Pass circuit, called Non-Polar Token-Pass Brownian Circuit, in which no such directional bias is assumed. Though most wires in such circuits do have directional bias, the few wires that don’t, allow for simpler circuit designs, as will be shown.
Ferdinand Peper, Jia Lee

On the Reversibility of ECAs with Fully Asynchronous Updating: The Recurrence Point of View

Abstract
The reversibility of classical cellular automata is now a well-studied topic but what is reversibility when the evolution of the system is stochastic? In this context, we study a particular form of reversibility: the possibility of returning infinitely often to the initial condition after a random number of time steps. This corresponds to the recurrence property of the system. We analyse this property for the 256 elementary cellular automata with a finite size and a fully asynchronous updating, that is, we update only one cell, randomly chosen, at each time step. We show that there are 46 recurrent rules which almost surely come back to their initial condition. We analyse the structure of the communication graph of the system and find that the number of the communication classes may have different scaling laws, depending on the active transitions of the rules (those for which the state of the cell is modified when an update occurs).
Nazim Fatès, Biswanath Sethi, Sukanta Das

An Overview of 2D Picture Array Generating Models Based on Membrane Computing

Abstract
A variety of two-dimensional array grammar models generating picture array languages have been introduced and investigated, utilizing and extending the well-established notions and techniques of formal string language theory. On the other hand the versatile computing model with a generic name of P system in the area of membrane computing, has turned out to be a rich framework for different kinds of problems in a variety of fields. Picture array generation in the field of two-dimensional (2D) languages is one such area where P systems with array objects and array rewriting, referred to as array P systems, have been fruitfully employed in increasing the generating power of the 2D grammar models. A variety of array P systems have been proposed in the literature. The objective of this survey is to review and describe the salient features of the major types of array P systems, which have served as the basis for developing other kinds of array P systems. Applications of these array P systems are also briefly described besides indicating possible new directions of investigation.
K. G. Subramanian, Sastha Sriram, Bosheng Song, Linqiang Pan

Input-Position-Restricted Models of Language Acceptors

Abstract
Machines of various types are studied with some restriction on the moves that can be made either on or before the end of the input. For example, for machine models such as deterministic reversal-bounded multicounter machines, one restriction is the class of all machines that do not subtract from any counters before the end the input. Similar restrictions are defined on different combinations of stores with many machine models (nondeterministic and deterministic), and their families studied.
Oscar H. Ibarra, Ian McQuillan

On the Persistency of Gellular Automata

Abstract
Gellular automata have been proposed as a new model of cellular automata that are intended to be implemented with gel materials. Computational universality has been investigated and has been shown with unidirectional signal propagation through Moritas rotary elements. A way to realize a Margolus neighborhood has also been proposed, so that block cellular automata can be realized directly in the model. In this chapter, the persistency of those results is examined with numerical simulations. It is shown that block cellular automata can undergo an infinite number of state transitions, and unidirectional signals can be transmitted repeatedly over a circuit. To show persistency, slight modifications of the proposed reactions are needed.
Masami Hagiya, Katsunobu Imai

Queue Automata: Foundations and Developments

Abstract
A queue automaton is basically a finite automaton equipped with a storage obeying the first-in-first-out principle, a queue. The power of queue automata has been studied from several perspectives. One of the classical results frequently cited in the literature is that a machine equipped with a queue storage can be capable of universal computations. This result has been discovered several times. At least implicitly it has already been mentioned by Post in 1943. In connection with formal languages, Vollmar studied in 1970 queue automata for the first time. Despite their versatility queue automata received only occasional attention, probably due to their high computational power with consequent low manageability. These facts triggered the study of subclasses and restricted variants of queue automata which documents the importance of these devices also from a practical point of view. In the present paper, we tour a fragment of the literature on queue automata to give a comprehensive overview of fundamental results and recent developments.
Martin Kutrib, Andreas Malcher, Matthias Wendlandt

Small Universal Reversible Counter Machines

Abstract
A k-counter machine (CM(k)) is an automaton with k counters as an auxiliary memory. It is known that CM(k) are universal for $$k\ge 2$$. As shown by Morita reversible CM(2) are universal. Based on results from Korec we construct four small universal reversible counter machines highlighting different trade-offs: (10, 109, 129), (11, 227, 270), (9, 97, 116) and (2, 1097, 1568), where in parentheses we indicated the number of counters, states and instructions, respectively. Since counter machines are used in many areas, our results can be the starting point for corresponding reversible universal constructions.
Artiom Alhazov, Sergey Verlan, Rudolf Freund

Improving the Success Probability for Shor’s Factorization Algorithm

Abstract
In Shor’s factorization algorithm (SFA), the task is to find a non-trivial factor of a given composite integer N. Briefly said, SFA works as follows. It chooses randomly an integer $$y<N$$ and checks whether y and N are co-primes. If y is co-prime with N, then SFA runs a special quantum subroutine to obtain the order 2r of N with a certain probability (2r is here an integer). In the original SFA and all previous SFAs, if 2r was an even integer and $$y^{r}\not \equiv -1(\text {mod}~N)$$, then SFA used y and 2r to get a non-trivial factor of N. However, if the result $$r'$$ obtained by the quantum order finding subroutine was not 2r, or 2r was not an even integer, or $$y^{r}\equiv -1(\text {mod}~N)$$, then the quantum subroutine had to be run again (and perhaps again and again). In this paper, we show that the three constraints are strong and the success probability for the quantum subroutine can be improved. In general, if a non-trivial factor of N can be got, we can call the result $$r'$$ an available result. Naturally, two issues arise: (1) If one of these constraints does not hold, whether these results $$r'$$ can also be used to make SFA succeed sometimes? (2) If there exist some other available results, then what is the success probability when these results are considered? This paper proves that some factorization results are still available or possible even if not all of the above constraints are met, and, in addition, that a new success probability can be bigger than those of the previous SFAs. Finally, in order to demonstrate a potential of our approach, we consider factorization of those integers N that are used as moduli for RSA, that is those N that are products of two safe primes, and we show that in this case the fault probability can be reduced to O(1 / N) with our method.
Guoliang Xu, Daowen Qiu, Xiangfu Zou, Jozef Gruska

Simple Block-Substitution Rule Exhibits Interesting Patterns

Abstract
The goal is to find all patterns (space-time evolutions) that can be generated by a simple binary 1D block substitution rule (BCA), the Twin-Toggle Rule. The 1D space is partitioned into even or odd cell pairs. The even and odd partition are alternated in time. If the two bits in a pair are equal, then they are substituted by their logical inverses. Firstly, all possible initial configurations are reduced to a set of representatives taking into account 0/1-inversion, cyclic shift and mirroring. Secondly, the BCA was simulated and all patterns were compared to each other for similarities (black/white-inversion, shift, rotation, mirroring). Only a small amount of them was stored, representing all possible patterns. Most of the patterns are single patterns (the pixel structure is the same for black and white pixels). For $$N = 8, 12$$ cells interesting dual patterns were discovered, which show a different structure for black and white pixels.
Rolf Hoffmann