2024-03-29T01:33:39Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000326302023-04-27T10:00:04Z01164:02592:02714:02716
計算万能な2次元16状態可逆的セル構造オートマトンのモデルComputation Universal Models of 2-Dimensional 16 - State Reversible Cellular Automatajpnhttp://id.nii.ac.jp/1001/00032630/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=32630&item_no=1&attribute_id=1&file_no=1Copyright (c) 1990 by the Information Processing Society of Japan山形大学工学部山形大学工学部上野, 聡森田, 憲一可逆的セル構造オートマトン()は"逆方向に決定的"なCA,即ち,全てのConfigurationに対して,直前のConfigurationが唯一つしか存在しないようなCAのことをいう.Margolusは,計算万能な2次元RCAのモデルで状態数が2のものが構成できることを示した.しかしながら,彼のモデルは,時間的,空間的に,多少の非一様性を持ち,標準的なCAの枠組みからは外れたものであった.本論文では,2次元可逆的PCA (rtitioned )と呼ぶ枠組みを用いて計算万能な16状態の単純なモデルを2つ示した.PCAは標準的なCAのサブクラスと見なせるので,これにより,16状態の標準的なRCAのモデルで計算万能なものが得られる.ここでは,各々のモデルについて,Fredkinゲートと呼ばれる.論理素子をシミュレー卜するconfigurationを与えた.Fredkinゲートが万能な論理素子であることから,これら2つのモデルの計算万能性が導かれる.A reversible (or injective) cellular automaton (RCA) is a "backward deterministic" CA, i.e., every configuration of it has at most one predecessor. Margolus has been shown that there is a computation-universal 2-dimensional 2-state RCA model. Although his model is very interesting, it differs from a standard CA model because it has somewhat spatial and temporal non-uniformity. In this paper, we show two kinds of simple 16-state computation-universal models using the framework of 2-dimesional reversible partitioned CE (PCA). Since PCA can be considered as a subclass of standard CA, we can obtain 16-state standard RCA models from them. For each of these models, we designed a configuration which simulates a Fredkin gate. As Fredkin gate is known to be a universal logic element, computation-universality of these two models is concluded.AN1009593X情報処理学会研究報告アルゴリズム(AL)199079(1990-AL-017)1251321990-09-282009-06-30