| Presentation | 1999/6/18 A simple Computer Embedded in a Reversible and Number-Conserving Two-Dimensional Cellular Space Kenichi MORITA, Yasuyuki TOJIMA, Katsunobu IMAI, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | We introduce a 4^4-stage two-dimensional reversible cellular automaton called P_4 having very simple state-transition rules. We show that any reversible two-counter machine can be embedded in a finite configuration of P_4 very concisely. Since a reversible two-counter machine is known to be universal, P_4 has thus universal computing ability. Besides reversibility, P_4 also satisfies the constraint of a number-conservation property, i. e., cells' states are represented by integers, and the total of the integers over the configuration is conserved throughout its evolving process. We give six kinds of basic elements for signal processing, and show that any reversible counter machine can be built only from them in P_4. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | cellular automata / computation-universality / reversibility / conservation law |
| Paper # | COMP99-21 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 1999/6/18(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A simple Computer Embedded in a Reversible and Number-Conserving Two-Dimensional Cellular Space |
| Sub Title (in English) | |
| Keyword(1) | cellular automata |
| Keyword(2) | computation-universality |
| Keyword(3) | reversibility |
| Keyword(4) | conservation law |
| 1st Author's Name | Kenichi MORITA |
| 1st Author's Affiliation | Faculty of Engineering, Hiroshima University() |
| 2nd Author's Name | Yasuyuki TOJIMA |
| 2nd Author's Affiliation | Faculty of Engineering, Hiroshima University |
| 3rd Author's Name | Katsunobu IMAI |
| 3rd Author's Affiliation | Faculty of Engineering, Hiroshima University |
| Date | 1999/6/18 |
| Paper # | COMP99-21 |
| Volume (vol) | vol.99 |
| Number (no) | 130 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |