Reversible Computing as a Future Computing System

点击翻译按钮获取中文摘要

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.