表題番号：2001B-009 日付：2003/05/12
研究課題構造的分子計算理論－自律的計算系の解析と設計のための基礎理論
研究者所属（当時） 資格 氏名
（代表者） 教育学部 教授 横森　貴
（連携研究者） 理工学部 教授 上田和紀
（連携研究者） 教育学部 助教授 楠元範明
研究成果概要
　研究実績の概要は以下の3つに分類される．

(1) 〈 自律的計算モデルの再考 〉
Adlemanによる有向ハミルトンパス問題(DHPP)に対するDNAを用いた解法を
基本として幾つかの自律的計算モデルが提案され，自律的計算系の計算論
的な万能性もよく知られているが，一般に，そこでは分子配列の設計という
問題が重要な要素を占める．本研究では，長さのみによる分子配列の設計
法に関して探究し，有限オートマトンやDHPPなどがそのような簡単な設計
によっても解決されることを示した.

(2) 〈 挿入・削除システムの解析 〉
DNAを用いた計算モデルのひとつとして挿入・削除システムが提案されて
いる．これは特定のDNA配列がある認識部位において挿入されたり，削除
される現象をモデル化したものであり，その計算能力は万能であることが
知られている．本研究では，このシステムが理論的に万能性を保持しながら
どこまで簡約化できるかを探究し，認識部位および挿入・削除記号列の
長さが共に１まで簡約化が可能であることを示した．

(3)〈 並列計算系による分子計算シミュレータの設計と試作 〉
分子計算系における局所的並列性をシリコン上で実装するために，
ノードの多重集合，膜とその階層化，リンク，グラフ変換の四概念に基づく新
たな計算モデル LMNtal の設計に着手し，基本設計をほぼ完了した．また，
Java を用いて試作処理系のコンパイラと
ランタイムを実装した．LMNtal は

1. 多重集合や会合概念をもった数多くの計算モデルの統合
2. リソースコンシャスな計算の基本モデル

などを目指したモデルであり，今年度は上記に加えて他の計算モデルとの比較
検討も進めた．