Theoretical Study on New Computing Mechanisms Based on Reversible Logic

与量子计算密切相关的可逆计算是研究未来计算系统可能性的一种非常重要的计算模型，现在是对其进行基础性和广泛性研究的时候了。(1)具有逻辑普适性的简单可逆元胞自动机：利用可逆元胞自动机的框架，研究逻辑电路和通用计算机如何从非常原始的可逆现象实现的问题。通过设计一个8态通用可逆元胞自动机，我们证明了任何逻辑电路的功能都可以简化为极其简单的可逆态转移函数。(2)保数可逆元胞自动机：我们研究了具有类似于物理(能量或质量)守恒定律的性质的元胞自动机。我们新定义了一种保数元胞自动机，并证明了它的计算能力。(3)可逆元胞自动机中的自复制：1997年我们已经给出了一个二维可逆元胞空间，在该空间中各种对象的自复制是可能的。我们将前面的模型扩展到三维，并证明了更多种类的对象的自我复制是可能的。(4)具有可逆性的语言和二维数组的生成系统：我们研究了几种唯一可解析的文法，它们具有与可逆系统相似的性质。我们给出了一类唯一可解析的文法，它准确地刻画了这类确定性上下文无关文法。我们还提出了一种简单的二维唯一可解析数组语法，它可以生成所有连通图片的集合。

"Reversible computing", which is closely related to quantum computing, 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 the standpoint, we studied reversible computing mechanisms theoretically, and obtained the following result.(1) A simple reversible cellular automation having logical universality :By using the framework of reversible cellular automata, we studied the problem how logic circuits and universal computers can be realized from very primitive reversible phenomena. We showed that functions of any logic circuits are reduced to extremely simple reversible state-transition function, by designing an 8-state universal reversible cellular automation.(2) A number-conserving reversible cellular automation :We studied cellular automata having a property similar to the conservation law (of energy or mass) in physics. We newly defined a number-conserving cellular automation, and proved its computation-university.(3) Self-reproduction in reversible cellular automata :We have already given a two-dimensional reversible cellular space in which self-reproduction of various objects is possible in 1997. We extended the previous model to three-dimension, and showed that self-reproduction of much larger variety of objects is possible.(4) Generating systems of languages and two-dimensional arrays having reversibility :We studied several kinds of uniquely parsable grammars, which have a similar property as reversible systems. We gave a class of uniquely parsable grammars that characterizes the class of deterministic context-free grammars exactly. We also proposed a simple two-dimensional uniquely parsable array grammar that generates the set of all connected pictures.