权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Reversible Computing as a Future Computing System

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

基本信息

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

项目摘要

Physical reversibility is one of the fundamental laws of Nature that governs microscopic behavior of the physical world. Since future computing devices will surely be implemented based on some physical phenomena of nano-scale level, it is an important problem how such property of Nature can be effectively used Reversible computing is a theoretical framework for studying computing models that reflect physical reversibility. From this standpoint, we investigated several reversible computing systems and some other related systems, and obtained the following results in the term 2004-2007.(1) We studied universality of simple reversible logic elements with one-bit memory (i.e., elements with 2 states), and proved that "all" the 14 elements that have 3 input/output lines and 2 states are logically universal.(2) We investigated how simple universal reversible Turing machines can be. In particular we designed a 17-state 5-symbol model that can simulate any cyclic tag system.(3) Simple universal reversible cellular automata are studied. It is shown that there is a 30-state 1-dimensional reversible cellular automaton that has computation-universality.(4) Relation between reversibility and asynchronism is studied. A simple construction method of a reversible cellular automaton out of asynchronous logic elements is shown.(5) Hyperbolic cellular automata, which are another model of physical space, is investigated. We showed that there is a 5-state model having computation-universality.(6) We studied and clarified relations among various models of reversible computing, and systematized the theory of reversible computing.

物理可逆性是自然界的基本定律之一，它支配着物理世界的微观行为。由于未来的计算设备必然是基于纳米级的物理现象来实现的，如何有效地利用自然界的这种特性是一个重要的问题。可逆计算是研究反映物理可逆性的计算模型的理论框架。从这个角度出发，我们在2004-2007年期间研究了几个可逆计算系统和其他一些相关系统，并得到了以下结果。(1)我们研究了具有一位存储器的简单可逆逻辑元件的通用性（即，具有2个状态的元素），并证明了具有3个输入/输出线和2个状态的“所有”14个元素在逻辑上是通用的。(2)我们研究了通用可逆图灵机有多简单。特别地，我们设计了一个17状态5符号模型，可以模拟任何循环标签系统。(3)研究了简单的通用可逆元胞自动机。结果表明，存在一个具有计算普适性的30态一维可逆元胞自动机。(4)研究了可逆性与非可逆性的关系。本文给出了一种用异步逻辑元件构造可逆元胞自动机的简单方法。(5)研究了另一种物理空间模型--双曲元胞自动机。我们证明了存在一个具有计算普适性的五态模型。(6)研究和澄清了各种可逆计算模型之间的关系，使可逆计算理论系统化。