Non-degenerate 2-State Reversible Logic Elements with Three or More Symbols Are All Universal
Kenichi Morita, Tsuyoshi Ogiro, Artiom Alhazoz and Tsuyoshi Tanizawa
A reversible logic element is a primitive from which reversible computing systems can be constructed. A rotary element is a typical one with 1-bit memory (hence it has 2 states) and with 4 input/output symbols. It is known that we can construct any reversible Turing machine by using only rotary elements very simply. In this sense it is a universal reversible logic element. There are also many other reversible elements with 1-bit memory. So far, it has been shown that all the 14 kinds of non-degenerate 2-state 3- symbol reversible elements can simulate a rotary element, and hence they are universal. In this paper, we generalize this result by showing that every non-degenerate 2-state k-symbol reversible logic element can simulate a rotary element if k > 2.
Keywords: reversible logic element, universality, reversible computing, rotary element, reversible Turing machine