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)研究了几种唯一可解析的语法系统。这些系统可以看作是异步可逆系统的一种。显示了它们的各种属性、与元胞自动机的关系、范式及其模式生成能力。