化学反応オートマトンの研究

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

研究代表者は，2012年にReaction Automata（RA）と呼ばれる多重集合変換に基づく化学反応系のモデルを提案している．RAの特徴として，入力として文字列を扱うことによって，化学反応系のもつ計算能力を理論的に解析できることが挙げられる．本研究では，RAを基本とする幾つかの変形モデルについて考察をし，抽象的な化学反応系によって計算可能なクラスを明らかにすることと共に，他の既存の反応計算モデルとの関係を解明することを目標とした．具体的には， 従来の極大並列的な適用によるRA（RAmp）に加え，逐次的な適用を用いたRA（RAsq）の計算能力について考察した．この際，(i)領域計算量による制限や，(ii)入力列の中に空文字を許すかどうかなどを考慮した．特に(ii)については，入力列の中に空文字を許さない場合，RAsqのクラスは，ある方法で領域計算量を制限されたTuring機械（制限Turing機械）のクラスに包含されることを示した．また，制限Turing機械は万能計算の能力をもたないことを示した．これは，（入力列の中に空文字を許さない）RAmpがTuring機械と等価であることと対照的な結果である．また，近年活発に研究されている計算モデルである細胞計算系（P System）とRAの関係についての結果を得ることができた．今後の研究課題として，RAの解析を継続するとともに，提案したモデルの妥当性を計算機シミュレーションによって検証することが挙げられる．この際，RAに確率を導入したモデルを考案し，解析することも重要であると考えられる．