A Simple Construction Method of a Reversible Finite Automaton out of Fredkin Gates, and Its Related Problem
A Simple Construction Method of a Reversible Finite Automaton out of Fredkin Gates, and Its Related Problem
复制标题
Fredkin门可逆有限自动机的简单构造方法及其相关问题
DOI：
--
复制
发表时间：
1990
期刊：
影响因子：
--
通讯作者：
K. Morita
中科院分区：
文献类型：
--
作者：
K. Morita
可逆有限自动机（RFA）是一种向后确定性自动机，即，如果给定其输出的逆序列，则它可以唯一地回溯其移动序列。在本文中，我们展示了一个简单的方法来构建一个RF A从Fredkin门，这是可逆的和位保存的逻辑门，和单位线（单位延迟）。用这种方法得到的电路是“无垃圾”的，因为它没有必须提供常数的输入，也没有输出垃圾信号。我们还表明，一个一维可逆分区元胞自动机，这是已知的计算通用，可以从Fredkin门和单位线作为一个封闭的（因此垃圾少）无限电路。
A reversible finite automaton (RFA) is a backward deterministic automaton, i.e., it can uniquely retrace its move sequence if the inverse sequence of its outputs is given. In this paper, we show a simple method to construct an RF A from Fredkin gates, which are reversible and bit-conserving logic gates, and unit wires (unit delays) . The resulting circuit obtained by this method is "garbage-less" in the sense that it has no inputs to which constants must be supplied nor outputs from which garbage signals are put out. We also show that a one-dimensional revers ible partitioned cellular automaton, which are known to be com putation universal, can be constructed from Fredkin gates and unit wires as a closed (thus garbage-less) infinite circuit.