WEKO3
アイテム
Computation Universality of One-Dimensional Reversible (Injective) Cellular Automata
https://hiroshima.repo.nii.ac.jp/records/2008959
https://hiroshima.repo.nii.ac.jp/records/2008959b2f95897-07d6-46be-b4a1-06fc414d76c1
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
TransIEICE_E72-6_758.pdf (343.2 KB)
|
| Item type | デフォルトアイテムタイプ_（フル）(1) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2023-03-18 | |||||||||
| タイトル | ||||||||||
| タイトル | Computation Universality of One-Dimensional Reversible (Injective) Cellular Automata | |||||||||
| 言語 | en | |||||||||
| 作成者 |
Morita, Kenichi
× Morita, Kenichi
× Harao, Masateru
|
|||||||||
| アクセス権 | ||||||||||
| アクセス権 | open access | |||||||||
| アクセス権URI | http://purl.org/coar/access_right/c_abf2 | |||||||||
| 権利情報 | ||||||||||
| 権利情報 | Copyright (c) 1989 IEICE | |||||||||
| 主題 | ||||||||||
| 主題Scheme | Other | |||||||||
| 主題 | reversible computing | |||||||||
| 主題 | ||||||||||
| 主題Scheme | Other | |||||||||
| 主題 | cellular automata | |||||||||
| 主題 | ||||||||||
| 主題Scheme | Other | |||||||||
| 主題 | 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. | |||||||||
| 言語 | en | |||||||||
| 出版者 | ||||||||||
| 出版者 | 電子情報通信学会 | |||||||||
| 言語 | ||||||||||
| 言語 | eng | |||||||||
| 資源タイプ | ||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||
| 資源タイプ | journal article | |||||||||
| 出版タイプ | ||||||||||
| 出版タイプ | VoR | |||||||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||||||
| 関連情報 | ||||||||||
| 識別子タイプ | 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/ | |||||||||
| 収録物識別子 | ||||||||||
| 収録物識別子タイプ | ISSN | |||||||||
| 収録物識別子 | 0913-574X | |||||||||
| 収録物識別子 | ||||||||||
| 収録物識別子タイプ | NCID | |||||||||
| 収録物識別子 | AA10684666 | |||||||||
| 開始ページ | ||||||||||
| 開始ページ | 758 | |||||||||
| 書誌情報 |
The Transactions of the IEICE The Transactions of the IEICE 巻 E72, 号 6, p. 758-762, 発行日 1989-06-25 |
|||||||||
| 旧ID | 48449 | |||||||||
