表題番号:2017K-121 日付:2018/02/24
研究課題反応オートマタ理論に基づく化学反応計算系の基礎的研究
研究者所属(当時) 資格 氏名
(代表者) 教育・総合科学学術院 教育学部 教授 横森 貴
研究成果概要

Chemical reaction automata (CRAs) are computing models with multiset storage based on multiset rewriting introduced in Okubo and Yokomori in 2014. A CRA consists of a finite set of reactions (or pairs of multisets called reactants and products, respectively) and an initial multiset as well as a set of final multisets. Taking an input symbol in the current configuration (multiset) a CRA changes it into a new configuration. Thus, a CRA offers an automaton-like computing model to investigate the computational   analysis of chemical reactions. On the other hand, since any (irreversible) Turing machine was proven by Bennett to be effectively simulated by a reversible Turing machine, reversible computing has become a research field that has been receiving increased attention. In this paper, we introduce the notions of determinism and reversibility into CRAs, and investigate the computational powers of those classes of CRAs in comparison with the language classes of Chomsky hierarchy. The computing power of reversible CRAs involves the physical realization of molecular programming of chemical reaction networks with DNA strand displacement system implementation, and therefore, it is of great significance to elucidate the computing capabilities of both deterministic and reversible CRAs from the theoretical viewpoint of molecular computing.