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.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・2. 181-191 (2000)

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

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态三角可逆细胞自动化”理论计算机科学。

K. Morita: "Encyclopedia : Electronics, Information and Communication Handbook (items of "cellular automation", "self-reproducing automation" and "reversible machine")"Ohm-sha. 1339 (1998)

K. Morita：“百科全书：电子、信息和通信手册（“细胞自动化”、“自我复制自动化”和“可逆机器”项目）“欧姆沙。