Computation-Universal Models of Two-Dimensional 16-State Reversible Cellular Automata
IEICE Transactions on Information and Systems E75-D 巻 1 号
141-147 頁
1992-01-25 発行
アクセス数 : 408 件
ダウンロード数 : 56 件
今月のアクセス数 : 0 件
今月のダウンロード数 : 0 件
この文献の参照には次のURLをご利用ください : https://ir.lib.hiroshima-u.ac.jp/00048451
| ファイル情報(添付) | |
| タイトル ( eng ) |
Computation-Universal Models of Two-Dimensional 16-State Reversible Cellular Automata
|
| 作成者 |
Ueno Satoshi
|
| 収録物名 |
IEICE Transactions on Information and Systems
|
| 巻 | E75-D |
| 号 | 1 |
| 開始ページ | 141 |
| 終了ページ | 147 |
| 抄録 |
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.
|
| 著者キーワード |
cellular automata
reversibility
computational universality
|
| 言語 |
英語
|
| 資源タイプ | 学術雑誌論文 |
| 出版者 |
電子情報通信学会
|
| 発行日 | 1992-01-25 |
| 権利情報 |
Copyright (c) 1992 IEICE
|
| 出版タイプ | Version of Record（出版社版。早期公開を含む） |
| アクセス権 | オープンアクセス |
| 収録物識別子 |
[NCID] AA10826272
[URI] https://search.ieice.org/bin/summary.php?id=e75-d_1_141&category=D&lang=E&year=1992&abst=
[URI] https://search.ieice.org/
[ISSN] 0916-8532
|
