可逆論理に基づく新しい計算機構の研究

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

可逆的な計算機構は、ミクロな物理現象を利用した発熱の非常に少ない理論素子による将来の計算システムの基礎となり得る。そのような観点から、数種の可逆計算機構の基本性質を理論的に研究し、次の成果を得た。1.可逆的物理空間のある種のモデルである可逆セル・オートマトンにおいて、いかなる高次機能がどれほど単純な可逆的素過程から発現できるのかという問題を研究した。(1)人工生命(Artificial Life)の分野でしばしば問題となる「自己増殖機能」が単純な可逆セル空間において実現できることを構成的に示した。自己増殖する物体の形状を動的に符号化する方式をとっているため、従来のC. Langtonのモデル等に比べ、簡単でかつ自由度が高い。自己増殖過程は作成したシュミレータで確認し、その動画ファイルをWWW上で公開している(http ://kepi.ke.sys.hiroshima-u. ac. jp/projects/rca/sr/)。(2)一斉射撃問題と呼ばれる同期問題が、可逆セル空間においても可能であることを証明した。ここでは特に、M. Minskyによる古典的解と同じ時間の解が、99状態の可逆セル空間で実現できることを示した。2.非常に単純な計算のモデルであるカウンタ機械の可逆化版について研究し、ただ2つのカウンタを持つ可逆カウンタ機械によって任意の計算が実行できること、つまりそれの計算万能性を証明した。「可逆性」の概念を生成文法の枠組みに導入した「一意解析可能文法」を新しく提案した。これは構文解析がバックトラックなしに実行できるような文法のクラスである。特に、それとその3つの部分族が「決定性Chomsky階層」を形成することを証明した。