このエントリーをはてなブックマークに追加
ID 48450
file
creator
subject
reversible computing
reversible sequential machine
Fredkin gate
abstract
A reversible finite automaton (RFA) is a backward deterministic automaton, i.e., it can uniquely retrace its move sequence if the inverse sequence of its outputs is given. In this paper, we show a simple method to construct an RFA from Fredkin gates, which are reversible and bit-conserving logic gates, and unit wires (unit delays). The resulting circuit obtained by this method is "garbage-less" in the sense that it has no inputs to which constants must be supplied nor outputs from which garbage signals are put out. We also show that a one-dimensional reversible partitioned cellular automaton, which are known to be computation universal, can be constructed from Fredkin gates and unit wires as a closed (thus garbage-less) infinite circuit.
journal title
The Transactions of the IEICE
volume
Volume E73
issue
Issue 6
start page
978
end page
984
date of issued
1990-06-25
publisher
電子情報通信学会
issn
0913-574X
ncid
language
eng
nii type
Journal Article
HU type
Journal Articles
DCMI type
text
format
application/pdf
text version
publisher
rights
Copyright (c) 1990 IEICE
relation url
department
Graduate School of Engineering