Theoretical Study on New Computing Mechanisms Based on Reversible Logic

基于可逆逻辑的新型计算机制的理论研究

• 批准号: 10680355
• 负责人: MORITA Kenichi
• 金额: $ 0.83万
• 依托单位: Hiroshima University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 1998
• 资助国家: 日本
• 起止时间: 1998 至 1999
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-10680355/
• 关键词: reversible computing; reversible logic; logical universality; reversible cellular automata; conservation law; self-reproducing automata; generative grammar; 計算万能性; アレイ文法

"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.

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

项目成果

K. Imai: "A computation-universal two-dimensional 8-state triangular reversible cellular automaton"Theoretical Computer Science. 231・2. 181-191 (2000)

K. Imai：“计算通用的二维8状态三角可逆元胞自动机”理论计算机科学231・2（2000）。

K.Morita: "Number-conserving reversible cellular automata and their computation-universality (invited talk)" Proc.of the MFCS'98 Workshop on Cellular Automata, Brno. 51-68 (1998)

K.Morita：“数守恒可逆元胞自动机及其计算通用性（受邀演讲）”Proc.of the MFCS98 元胞自动机研讨会，布尔诺。

Gh. Paun (ed.): "Recent Topics in Mathematical and Computational Linguistics"Publishing House of the Romanian Academy, Bucharest (to appear).

呃。

K.Imai: "A computation-universal two-dimensional 8-state triangular reversible cellular automaton"Theoretical Computer Science. 231. 181-191 (2000)

K.Imai：“计算通用的二维8态三角可逆元胞自动机”理论计算机科学。

K. Imai: "A computation-universal two-dimensional 8-state triangular reversible cellular automation"Theoretical Computer Science. Vol. 231, No. 2. 181-191 (2000)

K. Imai：“计算通用的二维8态三角可逆细胞自动化”理论计算机科学。