Theory of Reversible Computing
Theory of Reversible Computing
复制标题
DOI：
10.1007/978-4-431-56606-9
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
K. Morita
中科院分区：
文献类型：
--
作者：
K. Morita
可逆计算系统是一个“后向确定性”系统，使得系统的每个状态最多有一个前身。因此，没有一对不同的状态会进入同一状态。虽然它的定义很简单，但它与物理可逆性密切相关。可逆计算的研究起源于可逆和不可逆计算系统中能量耗散的研究。Rolf Landauer在他的论文“Inreversibility and heat generation in the computing process”（IBM J.Res.Dev.，Vol. 5，pp. 183-191，1961）。他指出，不可逆的逻辑运算不可避免地会导致计算系统中的能量耗散。从那时起，可逆计算就被研究与物理可逆性有关。除了计算中的能量耗散问题之外，重要的是要知道如何在计算中有效地利用可逆性。这是因为未来的计算设备肯定会直接通过纳米级的物理现象来实现，而可逆性是自然界基本的微观物理定律之一。为此目的，迄今为止已经提出并研究了各种可逆计算模型。在这本书中，可逆计算是从自动机和计算理论的角度研究的。我们处理各种可逆计算模型属于几个不同的水平，范围从微观到宏观一个。它们是可逆物理模型、可逆逻辑元件、由逻辑元件组成的可逆功能模块、可逆计算系统，如图灵机、元胞自动机等。这本书的目的是澄清如何计算可以进行有效和优雅地在这些可逆计算模型。我们将看到，即使是非常简单的可逆系统，尽管有可逆性的约束，也具有计算普适性。我们还将看到不同层次的各种可逆系统是相互关联的，即一个高层次的可逆系统可以由低层次的可逆系统构造出来。而且，施工方法往往非常独特，与传统方法中的施工方法不同。因此，这些计算模型以及设计方法将为我们提供新的见解，为未来的计算系统。VII
A reversible computing system is a “backward deterministic” system such that every state of the system has at most one predecessor. Hence, there is no pair of distinct states that go to the same state. Though its definition is so simple, it is closely related to physical reversibility. The study of reversible computing originated from an investigation of energy dissipation in reversible and irreversible computing systems. Rolf Landauer investigated the relation between reversibility in computing and reversibility in physics in his paper “Irreversibility and heat generation in the computing process”(IBM J. Res. Dev., Vol. 5, pp. 183–191, 1961). He pointed out that an irreversible logical operation inevitably causes energy dissipation in the computing system. Since then, reversible computing has been studied in relation to physical reversibility. Besides the problem of energy dissipation in computing, it is important to know how reversibility can be effectively utilized in computing. This is because future computing devices will surely be implemented directly by physical phenomena in the nano-scale level, and reversibility is one of the fundamental microscopic physical laws of Nature. For this purpose, various models of reversible computing have been proposed and investigated till now. In this book, reversible computing is studied from the standpoint of the theory of automata and computing. We deal with various reversible computing models belonging to several different levels, which range from a microscopic level to a macroscopic one. They are reversible physical models, reversible logic elements, reversible functional modules composed of logic elements, reversible computing systems such as Turing machines, cellular automata, and others. The purpose of this book is to clarify how computation can be carried out efficiently and elegantly in these reversible computing models. We shall see that even very simple reversible systems have computational universality in spite of the constraint of reversibility. We shall also see various reversible systems in different levels are related each other, ie, a reversible system in a higher level can be constructed out of those in a lower level. Moreover, the construction methods are often very unique and different from those in the traditional methods. Thus, these computing models as well as the designing methods will give us new insights for future computing systems. vii