このエントリーをはてなブックマークに追加
ID 48451
file
creator
Ueno, Satoshi
subject
cellular automata
reversibility
computational universality
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.
journal title
IEICE Transactions on Information and Systems
volume
Volume E75-D
issue
Issue 1
start page
141
end page
147
date of issued
1992-01-25
publisher
電子情報通信学会
issn
0916-8532
ncid
language
eng
nii type
Journal Article
HU type
Journal Articles
DCMI type
text
format
application/pdf
text version
publisher
rights
Copyright (c) 1992 IEICE
relation url
department
Graduate School of Engineering



Last 12 months's access : ? times
Last 12 months's DL: ? times


This month's access: ? times
This month's DL: ? times