Computation-Universal Models of Two-Dimensional 16-State Reversible Cellular Automata

IEICE Transactions on Information and Systems Volume E75-D Issue 1 Page 141-147 published_at 1992-01-25
アクセス数 : 420
ダウンロード数 : 61

今月のアクセス数 : 4
今月のダウンロード数 : 2
File
TransIEICE_E75-1_141.pdf 529 KB 種類 : fulltext
Title ( eng )
Computation-Universal Models of Two-Dimensional 16-State Reversible Cellular Automata
Creator
Ueno Satoshi
Source Title
IEICE Transactions on Information and Systems
Volume E75-D
Issue 1
Start Page 141
End Page 147
Abstract
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.
Keywords
cellular automata
reversibility
computational universality
Language
eng
Resource Type journal article
Publisher
電子情報通信学会
Date of Issued 1992-01-25
Rights
Copyright (c) 1992 IEICE
Publish Type Version of Record
Access Rights open access
Source Identifier
[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