General design of reversible sequential machines based on reversible logic elements

This paper proposes a scheme for decomposing reversible sequential machines (RSMs) into simple reversible logic elements (RLEs). This scheme is generalized from the previous constructions of reversible Turing machines (RTMs) using various RLEs (Lee et al. 2012), in which each RTM is composed by a uniform circuit of identical RSMs associated with two states. Each RSM's operation in the circuit, however, is subject to strict conditions that prevent direct extension of their constructions to more general RSMs. Our novel scheme to the contrary, imposes no condition on the operations of an RSM which may take any arbitrary number of states. Moreover, each RSM's construction can work asynchronously without a clock signal to synchronize all RLEs comprising the construction.