Theoretical Study on New Computing Mechanisms Based on Reversible Logic

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

"Reversible computing", which is closely related to quantum computing, 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 the standpoint, we studied reversible computing mechanisms theoretically, and obtained the following result.(1) A simple reversible cellular automation having logical universality :By using the framework of reversible cellular automata, we studied the problem how logic circuits and universal computers can be realized from very primitive reversible phenomena. We showed that functions of any logic circuits are reduced to extremely simple reversible state-transition function, by designing an 8-state universal reversible cellular automation.(2) A number-conserving reversible cellular automation :We studied cellular automata having a property similar to the conservation law (of energy or mass) in physics. We newly defined a number-conserving cellular automation, and proved its computation-university.(3) Self-reproduction in reversible cellular automata :We have already given a two-dimensional reversible cellular space in which self-reproduction of various objects is possible in 1997. We extended the previous model to three-dimension, and showed that self-reproduction of much larger variety of objects is possible.(4) Generating systems of languages and two-dimensional arrays having reversibility :We studied several kinds of uniquely parsable grammars, which have a similar property as reversible systems. We gave a class of uniquely parsable grammars that characterizes the class of deterministic context-free grammars exactly. We also proposed a simple two-dimensional uniquely parsable array grammar that generates the set of all connected pictures.