Reversible Computing as a Future Computing System

近年来，量子计算和DNA计算等所谓的“自然计算系统”受到了广泛的关注。可逆计算也是这样一种范式，具有类似于物理可逆性的性质，并且与量子计算密切相关。它是研究未来计算系统可能性的一个重要计算模型，现在是对它进行基础性和广泛性研究的时候了。从这个观点出发，我们研究了各种可逆计算系统和其他一些相关系统，并得到了以下结果。(1)A本文提出了一种称为“旋转元件”的通用可逆逻辑元件，并给出了一种基于它的可逆计算机的新结构。这种计算机的工作方式与传统计算机非常不同，并为可逆计算提供了新的见解。（2）给出了具有简单转移函数的可嵌入旋转元素的通用可逆元胞自动机。这表明可逆计算系统可以基于非常简单的可逆规则构建。（3）研究了具有数守恒性质的元胞自动机，这种性质类似于物理学中的质量守恒定律或能量守恒定律，并且与可逆性密切相关。这种系统具有计算的普遍性的简单模型。(4)It证明了在可逆的、数量守恒的细胞自动机中，像生物一样的自我复制是可能的。(5)研究了另一种物理空间模型--双曲元胞自动机。结果表明，这种系统具有高效率的计算能力。（6）研究了几个唯一可分析文法系统。这些系统可以看作是一类异步可逆系统。它们的各种性质，关系到细胞自动机，正常形式，和他们的模式生成能力。

Recently, much attention has been paid on so-called "Natural computing systems" like quantum computing and DNA computing. Reversible computing is also such a paradigm that has a property analogous to physical reversibility, and is closely related to quantum computing. It is a very important computing model to investigate the possibilities of future computing systems, and now is the time to make foundational and extensive researches on it for the future. From this standpoint, we studied various reversible computing systems and some other related systems, and obtained the following results.(1)A universal reversible logic element called "rotary element" is proposed, and a novel architecture for reversible computers based on it is shown. Such a computer works in a very different way than a conventional computer, and gives a new insight into reversible computing.(2)Universal reversible cellular automata having very simple transition functions in which rotary elements can be embedded are given. This shows reversible computing systems can be built based on extremely simple reversible rules.(3)Cellular automata having number-conserving property is studied, This property is an analogue of conservation law of mass or energy in physics, and has a close relation to reversibility. Simple models of such systems having computation-universality is shown.(4)It is shown that self-reproduction like living things is possible in reversible and number-conserving cellular automata.(5) Hyperbolic cellular automata, which are another model of physical space, is studied. It is shown that such systems have computing ability of high efficiency.(6)Several uniquely parsable grammar systems are studied. These systems can be regarded as kinds of asynchronous reversible systems. Various properties on them, relations to cellular automata, normal forms, and their pattern generating ability are shown.