より現実システムに近い非決定性モデルについて

概要

論文の詳細を見る
非決定性TM(NTM)やオルタネートTM(ATM)を純粋に数学モデルとする考え方もあるが、木構造でプロセスを生成していく並行システムのモデルとする見方もある。その場合のモデルの最大の特色は、生成された数多くのプロセスはいったん生成されたあとは一切相互干渉を持たないという点であろう。このような少ない通信量で、ATMの場合、T(n)時間でおよそT(n)領域量の直列計算を模擬できるという並行システムの基準ともいえる性質を有しており、モデルとしての優秀さは広く認められている。しかしこの特色は、別の(より現実的な)観点からは、並行システムとしては強すぎる制限にもなり、特に低いレベルの複雑さの具体的問題に対するアルゴリズム設計を考えるときは(もともと7M自身がそのような場合にあまりなじまない点を割引いて考えても)大きな障害になっているようでもある。以上の動機から、本稿では、ATMやNTMにおいてプロセス間通信を許すようなモデルの拡張を考える。通信機能としては最も原始的と考えられるバス通信をとり上げる。さらには、ATMから離れ、そのようなバス通信自体の並行システムにおける貢献についても考察する。
一般社団法人情報処理学会の論文
1986-10-01