Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben

2017 | Buch

Introduction Kapitel lesen Erstes Kapitel lesen

Theory of Reversible Computing

verfasst von: Kenichi Morita

Verlag: Springer Japan

Buchreihe : Monographs in Theoretical Computer Science. An EATCS Series

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

This book describes reversible computing from the standpoint of the theory of automata and computing. It investigates how reversibility can be effectively utilized in computing. A reversible computing system is a “backward deterministic” system such that every state of the system has at most one predecessor. Although its definition is very simple, it is closely related to physical reversibility, one of the fundamental microscopic laws of Nature. Authored by the leading scientist on the subject, this book serves as a valuable reference work for anyone working in reversible computation or in automata theory in general.

This work deals with various reversible computing models at several different levels, which range from the microscopic to the macroscopic, and aims to clarify how computation can be carried out efficiently and elegantly in these reversible computing models. Because the construction methods are often unique and different from those in the traditional methods, these computing models as well as the design methods provide new insights for future computing systems.

Organized bottom-up, the book starts with the lowest scale of reversible logic elements and circuits made from them. This is followed by reversible Turing machines, the most basic computationally universal machines, and some other types of reversible automata such as reversible multi-head automata and reversible counter machines. The text concludes with reversible cellular automata for massively parallel spatiotemporal computation. In order to help the reader have a clear understanding of each model, the presentations of all different models follow a similar pattern: the model is given in full detail, a short informal discussion is held on the role of different elements of the model, and an example with illustrations follows each model.

Inhaltsverzeichnis

Frontmatter
Chapter 1. Introduction
Abstract
Reversible computing is a paradigm that has a close relation to physical reversibility. Since microscopic physical laws are reversible, and future computing devices will surely be implemented directly by physical phenomena in the nano-scale level, it is an important problem to know how reversibility can be effectively utilized in computing. Reversible computing systems are defined as systems for which each of their computational configurations has at most one predecessor. Hence, they are “backward deterministic” systems. Though the definition is thus rather simple, these systems reflect physical reversibility very well, and they are suited for investigating how computing systems can be realized in reversible physical environments. In this chapter, we argue reversibility in physics and computing, the significance of reversible computing, and the scope of this volume. Various models of reversible computing ranging from a microscopic level to a macroscopic one are dealt with from the viewpoint of the theory of automata and computing. Terminologies and notations on logic, mathematics, and formal languages used in this volume are also summarized.
Kenichi Morita
Chapter 2. Reversible Logic Elements with Memory
Abstract
A reversible logic element with memory (RLEM) is presented as a logical primitive for constructing reversible computing systems. In the conventional design theory of logic circuits, logic gates, which are elements without memory, are mainly used as logical primitives. On the other hand, in the case of reversible computing, RLEMs are also useful as logical primitives. This is because reversible machines can be constructed easily and concisely by a simple RLEM. In addition, the design method using RLEMs is very different from those in the traditional theory of logic circuits based on logic gates. Thus RLEMs give new vistas and suggest various possibilities in the theory of reversible computing. Here, we present a typical 2-state 4-symbol RLEM called a rotary element (RE), and investigate how it is realized in the billiard ball model, a reversible physical model of computing, and how reversible sequential machines can be constructed from it.
Kenichi Morita
Chapter 3. Classification of Reversible Logic Elements with Memory and Their Universality
Abstract
A reversible logic element with memory (RLEM) is a logical primitive useful for composing reversible machines. It is a kind of reversible sequential machine (RSM), and thus has finite numbers of states and input/output symbols. First, we prove that every non-degenerate 2-state k-symbol RLEM is universal if k > 2. Hence, any RSM can be constructed by such a universal RLEM. On the other hand, it is shown that RLEMs Nos. 2-2, 2-3 and 2-4 among the four non-degenerate 2-state 2-symbol RLEMs are non-universal, and thus we obtain a simple hierarchy among 2-state RLEMs. We then show that there is a compact realization method of RSMs by RLEM 4-31 or RLEM 3-7. Hence, these RLEMs are useful for constructing reversible machines, as well as rotary element (RE), a typical 2-state 4-symbol RLEM. We also give a simple and systematic method of realizing a reversible 4-symbol RLEM with arbitrary number of states in the billiard ball model (BBM), a reversible physical model of computing.
Kenichi Morita
Chapter 4. Reversible Logic Gates
Abstract
A reversible logic gate is a memory-less logic element that realizes an injective logical function. Fredkin gate, Toffoli gate, interaction gate, and switch gate are typical ones. Here, we investigate basic properties of reversible logic gates and circuits, which are needed in the following chapters. First, logical universality of them is discussed. Then, a construction method of an almost garbage-less reversible combinatorial logic circuit is explained. Reducing the total amount of garbage signals is an important problem in designing reversible logic circuits. Finally, relations among Fredkin gate, reversible logic elements with 1-bit memory (RLEMs), and reversible sequential machines (RSM) are studied. In particular, it is shown that we can construct a completely garbage-less circuit out of Fredkin gates and delay elements that simulates a given RSM. This result will be used to show universality of reversible cellular automata in the later chapters.
Kenichi Morita
Chapter 5. Reversible Turing Machines
Abstract
A reversible Turing machine (RTM) is a basic model for studying computational universality, and computational complexity in reversible computing. In this chapter, after giving definitions on RTMs, we explain the method of Bennett for constructing a three-tape RTM that simulates a given irreversible TM. By this, computational universality of the class of three-tape RTMs is derived. We then clarify basic properties of RTMs, and study several variations of RTMs. In particular, we give simplification methods for RTMs. They are methods for reducing the number of tapes, the number of tape symbols, and the number of states of RTMs. From them, the computational universality of one-tape two-symbol RTMs with one-way infinite tape, and one-tape three state RTMs is derived. These results are useful for showing the computational universality of other reversible systems, and for composing reversible computing machines out of reversible logic elements.
Kenichi Morita
Chapter 6. Making Reversible Turing Machines from Reversible Primitives
Abstract
The problem how we can construct reversible Turing machines (RTMs) out of reversible primitives is investigated. It is shown that any one-tape two-symbol RTM can be concisely realized as a completely garbage-less reversible logic circuit composed of a rotary element (RE), or a reversible logic element with memory RLEM 4-31. Though we deal with only one-tape two-symbol RTMs in the quintuple form for simplicity, the construction method can be generalized for any type of RTMs. Here, an RTM is decomposed into a finite control module, and memory cells. Then, they are implemented as reversible sequential machines (RSMs) using RE or RLEM 4-31. The design methods employed here are quite different from those in the traditional design theory of logic circuits based on logic gates. Furthermore, since RE and RLEM 4-31 have simple realizations in the billiard ball model (BBM), an idealized reversible physical model, the constructed RTMs are further embeddable in BBM.
Kenichi Morita
Chapter 7. Universal Reversible Turing Machines
Abstract
In this chapter, the problem of finding small universal Turing machines (UTMs) that satisfy the reversibility condition is studied. Such UTMs are called universal reversible Turing machines (URTMs). Let URTM(m,n) denote an m-state n-symbol URTM.We give several URTM(m,n)’s with small m and n. Here, a method of simulating cyclic tag systems (CTSs) by URTMs is employed. A CTS is a kind of a very simple string rewriting system, and is known to be computationally universal. By this method, URTM(10,8), URTM(13,7), URTM(15,6), URTM(17,5), URTM(24,4), and URTM(32,3) are obtained. On the other hand, it is generally difficult to design small reversible TMs with two symbols or with a very small number of states. For these cases, we apply general conversion methods to some of the above small URTMs, and obtain URTM(138,2), URTM(4,168), and URTM(3, 36654).
Kenichi Morita
Chapter 8. Space-Bounded Reversible Turing Machines
Abstract
In this chapter, we investigate the problem how reversibility and determinism affect language accepting capability of space-bounded Turing machines (TM). A space-bounded TM is a model whose memory space is bounded by a space function S(n), where n is the input length. Here, we study the relationship among four classes of space-bounded TMs, i.e., irreversible nondeterministic (IN), irreversible deterministic (ID), reversible nondeterministic (RN), and reversible deterministic (RD) ones.We first show a very simple method of simulating an IDTM by an RDTM that uses the same numbers of storage tape symbols and storage tape squares. By a similar method, we also show that an RNTM that satisfies some condition can be simulated by an RDTM that uses the same numbers of storage tape symbols and storage tape squares. Therefore, IDTMs, RNTMs, and RDTMs with the same space function are equivalent in their language accepting powers, and thus an RDTM has relatively high capability in spite of the constraints of reversibility and determinism.
Kenichi Morita
Chapter 9. Other Models of Reversible Machines
Abstract
Besides reversible Turing machines, various models of reversible machines and automata have been proposed till now. They are reversible finite automata, reversible multi-head finite automata, reversible pushdown automata, reversible counter machines, reversible cellular automata, and others. In this chapter, reversible counter machines (RCMs), and reversible multi-head finite automata (RMFAs) are studied. Reversible cellular automata will be investigated in Chaps. 10–14. A CM is a computing machine that consists of a finite control and a finite number of counters. It is shown that an RCM with only two counters is computationally universal. This result is useful for proving the universality of other reversible systems, since it is a very simple model of computing. On the other hand, an MFA is an acceptor of a language that consists of a finite control, a read-only input tape, and a finite number of input heads. It is proved that any irreversible MFA can be converted into a reversible one with the same number of heads. Hence, the language accepting power of MFAs does not decrease with the constraint of reversibility.
Kenichi Morita
Chapter 10. Reversible Cellular Automata
Abstract
A cellular automaton (CA) is a discrete model for a spatiotemporal phenomenon. In a CA, an infinite number of cells are placed uniformly in the space, and each cell changes its state depending on its neighboring cells by a local function. Applying the local function to all the cells in parallel, a global function is induced, by which the configuration of the cellular space evolves. A reversible CA (RCA) is one whose global function is injective. It is thus considered as an abstract model of a reversible space.We use RCAs for studying how computation and information processing are performed in a reversible space. If we use the framework of classical CAs, however, it is generally difficult to design RCAs. Instead, we use the framework of partitioned cellular automata (PCAs). Based on it, various RCAs with interesting features and/or computational universality are designed in this and in the following chapters. It is also a useful model to investigate how complex phenomena appear from a very simple reversible local function. In this chapter, after giving basic properties of RCAs, methods of simulating irreversible CAs by reversible ones, and of constructing PCAs from reversible logic elements are shown.
Kenichi Morita
Chapter 11. One-Dimensional Universal Reversible Cellular Automata
Abstract
The problem of constructing Turing universal reversible one-dimensional cellular automata (RCAs) is studied. First, methods of designing three-neighbor and two-neighbor reversible partitioned CAs (RPCAs) that directly simulate a given reversible Turing machine (RTM) are shown. Since RPCAs are a subclass of RCAs, we see the class of one-dimensional RCAs is Turing universal even in the twoneighbor case. Next, the problem of finding one-dimensional RPCAs with a small number of states that can simulate any TM is investigated. The first model is a 24-state two-neighbor RPCA with ultimately periodic configurations, and the second one is a 98-state three-neighbor RPCA with finite configurations. Both of them can simulate any cyclic tag system, a kind of a universal string rewriting system. Finally, the computing power of reversible and number-conserving CAs (RNCCAs) are studied. The notion of number-conservation is a property analogous to the conservation law in physics. It is proved that there is a 96-state one-dimensional fourneighbor RNCCA that is Turing universal. Hence, the computing power of RCAs does not decrease even if the constraint of number-conservation is further added.
Kenichi Morita
Chapter 12. Two-Dimensional Universal Reversible Cellular Automata
Abstract
The problem of finding simple universal two-dimensional reversible cellular automata (RCAs) is studied. Here, three kinds of reversible partitioned CAs (RPCAs) are designed. The first two are 16-state RPCAs in which any circuit composed of Fredkin gates and delay elements is embeddable. Since a finite control and a tape cell of a reversible Turing machine can be composed of Fredkin gates and delay elements, these RPCAs with horizontally ultimately periodic configurations are Turing universal. A cell of any two-dimensional RPCA can also be constructed out of Fredkin gates and delay elements. Hence, these two models are intrinsically universal, as well as Turing universal, in the sense that any two-dimensional RPCA can be simulated in their cellular space. The last model is an 81-state RPCA, which is again both Turing universal, and intrinsically universal. Though the number of states is larger than those of the first two, any reversible two-counter machine is embedded concisely in its finite configurations.
Kenichi Morita
Chapter 13. Reversible Elementary Triangular Partitioned Cellular Automata
Abstract
A three-neighbor triangular partitioned cellular automaton (TPCA) is a CA such that each cell is triangular-shaped and has three parts. A TPCA is called an elementary TPCA (ETPCA), if it is rotation-symmetric, and each part of a cell has only two states. The class of ETPCAs is one of the simplest subclasses of twodimensional CAs, since the local function of each ETPCA is described by only four local rules. Here, we investigate the universality of reversible ETPCAs (RETPCAs). First, nine kinds of conservative RETPCAs, in which the total number of particles is conserved in their evolution processes, are studied. It is proved that six conservative RETPCAs among nine are Turing universal and intrinsically universal by showing any reversible logic circuit composed of Fredkin gates can be simulated in them. It is also shown that three conservative RETPCAs among nine are non-universal. Next, we study a specific non-conservative RETPCA T0347, where 0347 is its identification number in the class of 256 ETPCAs. In spite of its simplicity it exhibits complex behavior like the Game of Life CA. Using gliders to represent signals, Turing universality and intrinsic universality of T0347 are also proved.
Kenichi Morita
Chapter 14. Self-reproduction in Reversible Cellular Automata
Abstract
J. von Neumann first showed that machine self-reproduction is possible using the framework of cellular automaton (CA). In his CA, self-reproducing objects have universality in both computing and construction, and thus they were very complex. Later, Langton relaxed this condition, and designed a simple selfreproducing automaton. In this chapter, we study how self-reproducing automata are constructed in a reversible environment. It is shown that there are two- and threedimensional reversible cellular automata (RCAs), in which various objects called Worms and Loops can self-reproduce. Hence, Langton’s type self-reproduction is possible in RCAs. There, conversion between a shape of an object and its description (or gene), and copying the description are done reversibly. Using these properties, self-reproducing automata are designed in RCAs. An additional advantage of them is that the “shape-encoding mechanism” is employed, i.e., the shape of a Worm or a Loop is encoded into its description in a reversible way. This makes the whole mechanism simple, and increases the variety of self-reproducing objects.
Kenichi Morita
Backmatter
Metadaten
Titel
Theory of Reversible Computing
verfasst von
Kenichi Morita
Copyright-Jahr
2017
Verlag
Springer Japan
Electronic ISBN
978-4-431-56606-9
Print ISBN
978-4-431-56604-5
DOI
https://doi.org/10.1007/978-4-431-56606-9

Premium Partner

    Bildnachweise