可逆的・保存的2次元セル空間への単純なコンピュータの埋め込み
スポンサーリンク
概要
- 論文の詳細を見る
2次元可逆セル・オートマトンで非常に単純な遷移規則を持つ4^4状態モデルP_4を提案し、その空間に任意の可逆2カウンタ機械が簡潔に埋め込めることを示す。可逆2カウンタ機械の計算万能性は既に知られているので、これによりP_4の万能性が導かれる。P_4は可逆性に加え、物理的な保存性に対応する性質も持っている:つまり、各セルの状態を表す非負整数の合計が計算過程全体を通じて一定値を保つ。ここでは、P_4中での信号の処理・操作用に6種の素子を設計し、可逆2カウンタ機械がこれらの素子だけから構成できることを示す。
- 1999-06-18
著者
関連論文
- 万能可逆チューリング機械の一構成法 (計算機科学基礎理論とその応用)
- A note on tatami tilings (アルゴリズムと計算機科学の数理的基盤とその応用--RIMS研究集会報告集)
- 非決定性チューリング機械の厳密な領域階層定理(情報・システム基礎)
- 4状態可逆チューリング機械の構成法 (理論計算機科学の深化 : 新たな計算世界観を求めて)
- A-6-6 有限可逆セルオートマトンの軌道(A-6.情報理論,一般セッション)
- 単純な非同期論理素子による同期可逆セルオートマトンの構成法(オートマトン・言語理論)
- 同期可逆セルオートマトンを実現できる非同期セル空間
- 単純な非同期論理素子による同期可逆セルオートマトンの構成法
- 非同期セル空間における順序機械構成
- 自己参照メカニズムに基づく自己増殖セルオートマトンのシミュレーション(ディジタルデータ付き論文特集)