Computation Universality of One-Dimensional Reversible (Injective) Cellular Automata
The Transactions of the IEICE E72 巻 6 号
758-762 頁
1989-06-25 発行
アクセス数 : 516 件
ダウンロード数 : 150 件
今月のアクセス数 : 5 件
今月のダウンロード数 : 1 件
この文献の参照には次のURLをご利用ください : https://ir.lib.hiroshima-u.ac.jp/00048449
| ファイル情報(添付) | |
| タイトル ( eng ) |
Computation Universality of One-Dimensional Reversible (Injective) Cellular Automata
|
| 作成者 |
Harao Masateru
|
| 収録物名 |
The Transactions of the IEICE
|
| 巻 | E72 |
| 号 | 6 |
| 開始ページ | 758 |
| 終了ページ | 762 |
| 抄録 |
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.
|
| 著者キーワード |
reversible computing
cellular automata
computational universality
|
| 言語 |
英語
|
| 資源タイプ | 学術雑誌論文 |
| 出版者 |
電子情報通信学会
|
| 発行日 | 1989-06-25 |
| 権利情報 |
Copyright (c) 1989 IEICE
|
| 出版タイプ | Version of Record（出版社版。早期公開を含む） |
| アクセス権 | オープンアクセス |
| 収録物識別子 |
[ISSN] 0913-574X
[NCID] AA10684666
[URI] https://search.ieice.org/bin/summary.php?id=e72-e_6_758&category=E&lang=E&year=1989&abst=
[URI] https://search.ieice.org/
|
