Reversible Computing as a Future Computing System

物理可逆性是支配物理世界微观行为的基本自然规律之一。由于未来的计算设备必然是基于一些纳米级的物理现象来实现的，如何有效地利用自然的这种性质是一个重要的问题。可逆计算是研究反映物理可逆性的计算模型的理论框架。从这个角度出发，我们研究了几个可逆计算系统和其他相关系统，并在2004-2007年期间得到了以下结果：(1)我们研究了具有一位记忆的简单可逆逻辑元件(即具有2个状态的元件)的普适性，证明了具有3条输入/输出线和2个状态的14个元件在逻辑上是通用的。(2)我们研究了通用可逆图灵机的简单程度。特别是，我们设计了一个可以模拟任何循环标签系统的17态5符号模型。(3)研究了简单的通用可逆元胞自动机。证明了存在一个具有计算普适性的30态一维可逆元胞自动机。(4)研究了可逆性与异步性的关系。给出了一种用异步逻辑元素构造可逆元胞自动机的简单方法。(5)研究了物理空间的另一种模型--双曲元胞自动机。我们证明了存在一个具有计算普适性的五态模型。(6)研究和澄清了各种可逆计算模型之间的关系，使可逆计算理论系统化。

Physical reversibility is one of the fundamental laws of Nature that governs microscopic behavior of the physical world. Since future computing devices will surely be implemented based on some physical phenomena of nano-scale level, it is an important problem how such property of Nature can be effectively used Reversible computing is a theoretical framework for studying computing models that reflect physical reversibility. From this standpoint, we investigated several reversible computing systems and some other related systems, and obtained the following results in the term 2004-2007.(1) We studied universality of simple reversible logic elements with one-bit memory (i.e., elements with 2 states), and proved that "all" the 14 elements that have 3 input/output lines and 2 states are logically universal.(2) We investigated how simple universal reversible Turing machines can be. In particular we designed a 17-state 5-symbol model that can simulate any cyclic tag system.(3) Simple universal reversible cellular automata are studied. It is shown that there is a 30-state 1-dimensional reversible cellular automaton that has computation-universality.(4) Relation between reversibility and asynchronism is studied. A simple construction method of a reversible cellular automaton out of asynchronous logic elements is shown.(5) Hyperbolic cellular automata, which are another model of physical space, is investigated. We showed that there is a 5-state model having computation-universality.(6) We studied and clarified relations among various models of reversible computing, and systematized the theory of reversible computing.