Design of 1-tape 2-symbol reversible Turing machines based on reversible logic elements

摘要

This paper proposes a novel scheme for constructing reversible Turing machines (RTMs) via various reversible logic elements. A reversible logic element is similar to a conventional reversible logic gate, except that the element also carries a 1-bit memory that can store binary states. The usage of internal states allows much more efficient and straightforward constructions of RTMs based on reversible elements than based on reversible logic gates. In particular, a remarkable feature of our constructions is that they can operate asynchronously, whereby the clock signal, which is indispensable for synchronizing all elements as in a reversible logic circuit, can possibly be removed from the construction.