Universality Problems on Reversible Logic Elements with 1-Bit Memory
Yuta Mukai, Tsuyoshi Ogiro and Kenichi Morita
A reversible logic element with memory (RLEM) is a primitive for constructing reversible computing machines. Different from a reversible logic gate, an RLEM has a finite amount of memory, and thus it is defined as a reversible sequential machine (RSM). An RLEM is called universal if any RSM can be realized as a circuit composed only of copies of it. It is known that reversible Turing machines are also constructed by a universal RLEM. In this paper, we study universality problems of 2-state RLEMs, i.e., RLEMs with 1-bit memory. It has been shown that every non-degenerate 2-state RLEMs with kinput/ output symbols is universal if k > 2. Here, we investigate whether non degenerate 2-state 2-symbol RLEMs are universal or not. There are four such RLEMs, which have ID numbers 2-2, 2-3, 2-4, and 2-17. We prove that RLEMs 2-2, 2-3, and 2-4 are non-universal. We also show that RLEM 2-2 is the weakest one among 2-state RLEMs. On the other hand, it is proved that any two combination among the three RLEMs 2-3, 2-4, and 2-17 is universal. By above, capability of all the 2-state RLEMs except 2-17 is clarified, and thus a simple hierarchy among them is obtained.
Keywords: Reversible computing, reversible logic element, reversible sequential machine, reversible finite automaton, universality