表題番号：2012B-050 日付：2013/02/28
研究課題生命言語理論に基づく生体分子の進化モデルの研究
研究者所属（当時） 資格 氏名
（代表者） 教育・総合科学学術院 教授 横森　貴
（連携研究者） 教育・総合科学学術院 助手 大久保文哉
研究成果概要
申請者らはここ数年来，化学反応系をモデル化した計算システムの理論的解析を行っている．
一般に，化学反応には反応分子(R), 抑制分子(I), 生成分子(P)の３つが関わるとして抽象化
し，これを多重集合の３つ，組a=(R,I,P)で定式化した．この反応の解釈は『いま考えている
分子の多重集合TはRを含むがIは含まないとき，この反応によりTからRが消費され，同時にP
が新たに生成される』とみなす．このとき反応aによりTから新たにT'(=T-R+P)が生成される．
このような反応aをすべて可能な限り適用するような反応の多重集合をαしたとき，αを極大並列
適用とよび，このときの変化を T⇒α T' と表す．
　このような形式化において，外部からの入力をも受け取りつつ，内部状態が遷移するオート
マトンを反応オートマトン(RA: Reaction Automata)として定義した．すなわち，外部入力列
a1,...,anがRA:Mによって受理されるとは，指定された状態の多重集合T0から，指定され
た最終状態の多重集合Fへ至る遷移の系列：T0⇒a1 T1⇒a2 T2 ⇒・・・⇒an Tn⇒・・・⇒Fが
存在するときと定義する（ただし，ここでは各遷移における極大並列反応は省略されている）．
そして，このように受理される入力列全体からなる集合L(M)の数学的性質（計算量）を理論的に
解析した．RAは化学反応系をモデル化した記号列受理器であり，（従来型のオートマトンと異
なり）試験管内や細胞内の環境を想定した“多重集合(multiset)”を扱う計算モデルという特徴
がある．得られた結果は以下の通りである．
　入力のサイズnをパラメタとしたとき，RAが計算に用いる多重集合のサイズを関数f(n)とする．
この時，
(i) f(n)が指数関数であるようなRAによって受理される集合の族は，文脈依存言語族CSLに一致する．
(ⅱ)f(n)が線形関数であり，かつ空入力動作が許されたRAによって受理される集合族は抽象言語族
(AFL)を形成する．
(ⅲ) 任意の帰納的可算言語は，f(n)が線形関数のRAによって受理される言語の準同型写像によって
表される．（以上，文献[1])

さらに，上記の状態遷移関係 ⇒a を逐次的な反応に制限した場合（s-RAと表す）の受理能力を解析した．
その結果，
(ⅳ）f(n)が線形関数で，空入力動作をもつs-RAによって受理される言語族は，１方向log f(n)空間
限定TMによって受理される言語族と一致する．
(ⅴ) f(n)が線形関数であるとき，RAとs-RAとはその受理能力は比較不能な関係にある．（以上，文献[2]）

これらの結果は，化学反応による計算/情報処理能力を解明する新しい知見を与える．