このエントリーをはてなブックマークに追加
ID 48449
本文ファイル
著者
Harao, Masateru
キーワード
reversible computing
cellular automata
computational universality
抄録(英)
A reversible cellular automaton (CA) is a "backward deterministic" CA, i.e, every configuration of it has at most one predecessor. Toffoli showed that a two-dimensional reversible cellular automaton is computation universal. He posed an open problem whether a one-dimensional reversible CA is computation universal. In this paper, we solve this problem affirmatively. This result is proved by using the previous result of Morita et al. that a 1-tape reversible Turing machine is computation universal. We give a construction method of a reversible CA which simulates a given 1-tape reversible Turing machine. To do this, we introduce a "one-dimensional partitioned cellular automaton" (1-PCA). 1-PCA has the property that the local reversibility (i.e., injectivity of a local function) is equivalent to the global reversibility, and thus it facilitates to design a reversible CA.
掲載誌名
The Transactions of the IEICE
E72巻
6号
開始ページ
758
終了ページ
762
出版年月日
1989-06-25
出版者
電子情報通信学会
ISSN
0913-574X
NCID
言語
英語
NII資源タイプ
学術雑誌論文
広大資料タイプ
学術雑誌論文
DCMIタイプ
text
フォーマット
application/pdf
著者版フラグ
publisher
権利情報
Copyright (c) 1989 IEICE
関連情報URL
部局名
工学研究科