| Presentation | 2004-09-17 Nondegenerate 2-State 3-Symbol Reversible Logic Elements Are All Universal Tsuyoshi OGIRO, Atsushi KANNO, Keiji TANAKA, Hiroko KATO, Kenichi MORITA, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | In the investigation of minimal machinery in reversible computing, we proved that each nondegenerate 2-state 3-symbol reversible logic element is logically universal. So far, a 2-state 4-symbol element called "rotary element" was shown to be logically universal in the framework of reversible logic element with memory. The main result in this paper not only improves the previous result with respect to the number of symbols, but also shows all the 2-state 3-symbol reversible logic elements except degenerate ones are logically universal. It is known that there are 24 essentially different 2-state 3-symbol reversible logic elements. Among them, 10 are degenerate ones, which are equivalent to 2-state 2-symbol ones or simple connecting wires. The other 14 are nondegenerate ones, and thus they are "proper" 2-state 3-symbol reversible logic elements. For each of the 14 elements we construct a circuit composed only of it that simulates a Fredkin gate, a logically universal gate. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | reversible logic element / logical universality / Fredkin gate / reversible computing |
| Paper # | COMP2004-28 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2004/9/10(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) | Nondegenerate 2-State 3-Symbol Reversible Logic Elements Are All Universal |
| Sub Title (in English) | |
| Keyword(1) | reversible logic element |
| Keyword(2) | logical universality |
| Keyword(3) | Fredkin gate |
| Keyword(4) | reversible computing |
| 1st Author's Name | Tsuyoshi OGIRO |
| 1st Author's Affiliation | Hiroshima University, Graduate School of Engineering() |
| 2nd Author's Name | Atsushi KANNO |
| 2nd Author's Affiliation | Hiroshima University, Graduate School of Engineering |
| 3rd Author's Name | Keiji TANAKA |
| 3rd Author's Affiliation | Hiroshima University, Graduate School of Engineering |
| 4th Author's Name | Hiroko KATO |
| 4th Author's Affiliation | Hiroshima University, Graduate School of Engineering |
| 5th Author's Name | Kenichi MORITA |
| 5th Author's Affiliation | Hiroshima University, Graduate School of Engineering |
| Date | 2004-09-17 |
| Paper # | COMP2004-28 |
| Volume (vol) | vol.104 |
| Number (no) | 317 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |