Nondegenerate 2-State 3-Symbol Reversible Logic Elements Are All Universal
Nondegenerate 2-State 3-Symbol Reversible Logic Elements Are All Universal
复制标题
DOI：
--
复制
发表时间：
2004-09
期刊：
影响因子：
--
通讯作者：
Tsuyoshi Ogiro;Atsushi Kanno;Keiji Tanaka;Hiroko Kato;Kenichi Morita
中科院分区：
文献类型：
--
作者：
Tsuyoshi Ogiro;Atsushi Kanno;Keiji Tanaka;Hiroko Kato;Kenichi Morita
在研究可逆计算中的最小机器时，我们证明了每个非退化的2状态3符号可逆逻辑元素在逻辑上是通用的。到目前为止，在带记忆的可逆逻辑元件的框架中，一种称为旋转元件的二态四符号元件在逻辑上是通用的。本文的主要结果不仅在符号个数方面改进了以前的结果，而且证明了除简并逻辑元件外，所有的2态3符号可逆逻辑元件都是逻辑通用的。已知存在24个基本上不同的2状态3符号可逆逻辑元件。其中10个为简并电路，相当于2态2符号电路或简单连接线。另外14个是非简并的，因此它们是“适当的”2状态3符号可逆逻辑元件。对于这14个元素中的每一个，我们构建了一个仅由它组成的电路，该电路模拟了Fredkin门，即逻辑上通用的门。
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.