表題番号：2013A-6159
日付：2014/03/15
研究課題多重集合理論に基づく計算システムの研究
| 研究者所属（当時） | 資格 | 氏名 | |
|---|---|---|---|
| （代表者） | 教育・総合科学学術院 | 教授 | 横森 貴 |
- 研究成果概要
- 申請者らはここ数年来，化学反応系をモデル化した計算システムの理論的解析を行って来た．
その結果，少数分子を扱う分子反応系は一般に「分子をふくむ溶液を多重集合とみなすこと
により，計算過程を多重集合の“置き換え系”としてモデル化できる」ことを確認した．
これらの知見から，多重集合を計算の作業領域（メモリ領域）とするオートマトン・モデル
という着想に至り，これをFinite Automata with Multiset Memory(FAMM)として，定式化
した．
FAMMは有限個の状態を有し，多重集合をメモリとして使用する記号列受理機構である．
よってFAMMは，これまで申請者らが研究してきたReaction Automata(RA)のヴァリアント
（変種）としてみなすことができる．より具体的には，FAMMの動作は以下のように説明される．
「今、状態がpでありメモリが多重集合Tであるとき，入力テープwから１記号ずつ入力記号a
を読み込む．そのとき，遷移規則(p, a, α)→(q,β)が適用されると，次の状態はqとなり
メモリーはT'(=T-α+β)への更新される．」与えられた入力列wの先頭から１記号ずつ読み
込んでいき，この動作を繰り返して行き，入力をすべて読み終えた後，ある（指定された）
最終状態へ遷移するとき，FAMMは入力列wを受理する．このようにして受理される入力列全体
の集合が本研究の対象である．
FAMMの研究目的は，「メモリとして多重集合のみを許される有限オートマトンの計算能力
を解析する」ことである．この研究テーマに関する予想として「多重集合というが概念が情報
を保持するデータ構造として極めてシンプルである（すなわち，記号列のような記号の順序
情報が保持できない）ことから，FAMMの計算能力は限られている」と思われていた．ところが
研究の結果，以下のような興味深い成果が得られている．
(1)（制限のない一般形の）FAMMの計算能力はチューリング機械と等価である．（すなわち，
現在の計算機と理論的に同等の能力を有する．）
(2) メモリを入力サイズの多項式サイズに制限したFAMMは線形有界オートマトンと等価な計算
能力をもつ
(3) 遷移規則の適用モードをハイプリッドにした、制限されたFAMMはプッシュダウンオートマトン
と等価な計算能力をもつ
(4) ある定数で抑えられたメモリをもつFAMMは有限オートマトンと等価である．
このように，FAMMという形式的枠組みにを用いて，従来から研究が行われている計算モデルで
あるチューリング機械を中核とするオートマトン理論を再構築することができた．
これらの結果は，多重集合による計算/情報処理能力を解明する新しい知見を与えている(文献[1]).