このエントリーをはてなブックマークに追加
ID 48450
本文ファイル
著者
キーワード
reversible computing
reversible sequential machine
Fredkin gate
抄録(英)
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.
掲載誌名
The Transactions of the IEICE
E73巻
6号
開始ページ
978
終了ページ
984
出版年月日
1990-06-25
出版者
電子情報通信学会
ISSN
0913-574X
NCID
言語
英語
NII資源タイプ
学術雑誌論文
広大資料タイプ
学術雑誌論文
DCMIタイプ
text
フォーマット
application/pdf
著者版フラグ
publisher
権利情報
Copyright (c) 1990 IEICE
関連情報URL
部局名
工学研究科