生物に基づく計算システムと可逆コンピューティングの理論

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

細胞膜計算システム(Pシステム)は、細胞内の物質の結合・解離や細胞間の物質の移動などを抽象化した計算モデルであり、自然計算(Natural computing)の一分野である。昨年度に続きこのシステムの諸性質、特に計算万能性に関する性質を明らかにするとともに、やはり自然計算の分野に属する可逆コンピューティングや保存的コンピューティングとの接点についての研究も行い、以下の結果を得た。1.Pシステム、特に多重集合書換システムと、それに対する可逆性の導入細胞膜が1つであるようなPシステムは、多重集合書換システムとして定式化できる。このようなシステムを計算万能性を保持したままどのように単純化できるかをいくつかの視点から明らかにした。一方、そのようなシステムに対して物理的な可逆性に相当する制約や決定性制約を加えた場合に計算万能となるための十分条件を与えた。2.可逆論理素子の計算万能性昨年度に示した、14種類の2状態3記号可逆論理素子がすべて計算万能になるという成果を大幅に拡張し、k>2の場合にはあらゆる2状態k記号可逆論理素子がすべて計算万能になるという結果を導いた。3.保存的セルオートマトンの近傍半径の縮小物質やエネルギーの保存則に相当する性質を持つセルオートマトンの近傍半径を1/2にまで縮小できることを証明した。これにより、この種のセルオートマトンも計算万能性を有することが結論できる。