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)研究并阐明了可逆计算的各种模型之间的关系，系统化了可逆计算的理论。