Reversible Computing as a Future Computing System

可逆计算作为未来的计算系统

基本信息

批准号：
12680353
负责人：
MORITA Kenichi
金额：
$ 1.92万
依托单位：
HIROSHIMA UNIVERSIlY
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2000
资助国家：
日本
起止时间：
2000 至 2003
项目状态：
已结题

项目摘要

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.

最近，已经对所谓的“自然计算系统”（如量子计算和DNA计算）引起了很多关注。可逆计算也是具有类似于物理可逆性的属性的范式，并且与量子计算密切相关。这是一个非常重要的计算模型，可以研究未来计算系统的可能性，现在是时候对未来进行基础和广泛的研究了。从这个角度来看，我们研究了各种可逆的计算系统和其他相关系统，并获得了以下结果。（1）提出了一种通用可逆逻辑元素，称为“旋转元素”，并显示了基于它的可逆计算机的新型体系结构。这样的计算机与常规计算机的工作方式非常不同，并为可逆计算提供了新的见解。（2）具有非常简单的过渡函数的通用可逆蜂窝自动机，其中可以嵌入旋转元素。这表明可以基于极其简单的可逆规则来构建可逆计算系统。（3）研究了具有数字支持属性的蜂窝自动机，该属性是物理学中质量或能量的一种类似物，并且与可逆性有着密切的关系。显示了具有计算通用性的此类系统的简单模型。（4）表明，在可逆且持有数量的蜂窝自动机中，可以使用像生物这样的自我生产。（5）研究了另一种是物理空间模型的双曲线细胞自动机。结果表明，此类系统具有高效率的计算能力。（6）研究了几种独特的可拆卸语法系统。这些系统可以被视为异步可逆系统。显示了各种特性，与蜂窝自动机的关系，正常形式及其模式产生能力。