このエントリーをはてなブックマークに追加
ID 48451
本文ファイル
著者
Ueno, Satoshi
キーワード
cellular automata
reversibility
computational universality
抄録(英)
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 two-dimensional 2-state RC A model. Although his model is very interesting, it differs from a standard CA model because of its somewhat spatial and temporal non-uniformity. In this paper, we present two kinds of simple 16-state computation-universal models using the framework of two-dimensional reversible partitioned CA (PCA). Since PCA can be considered as a subclass of standard CA, we can immediately obtain 16-state standard RCA models from them. For each of these models, we designed a configuration which simulates a Fredkin gate. Since Fredkin gate has been known to be a universal logic element, computation-universality of these two models is concluded.
掲載誌名
IEICE Transactions on Information and Systems
E75-D巻
1号
開始ページ
141
終了ページ
147
出版年月日
1992-01-25
出版者
電子情報通信学会
ISSN
0916-8532
NCID
言語
英語
NII資源タイプ
学術雑誌論文
広大資料タイプ
学術雑誌論文
DCMIタイプ
text
フォーマット
application/pdf
著者版フラグ
publisher
権利情報
Copyright (c) 1992 IEICE
関連情報URL
部局名
工学研究科