Realizing Reversible Logic Elements with Memory in the Billiard Ball Model
Yuuta Mukai and Kenichi Morita
Reversible computing is a paradigm of computation that reflects physical reversibility. It has a close relation to quantum computing, since evolution of a quantum system is reversible. Various reversible logic elements have been studied until now as building primitives for reversible computers. There are two kinds of such elements: those without memory, which are usually called reversible gates, and those with memory. A rotary element is a typical reversible logic element with 1-bit (i.e., 2-state) memory, from which any reversible Turing machine can be constructed easily. It has been shown that a rotary element can be realized in the billiard ball model very simply, which is an ideal mechanical model having physical reversibility. On the other hand, there are also many other kinds of reversible logic elements with memory. Here we show that any 4-symbol reversible logic element with an arbitrary number of states can be realized in the billiard ball model by a simple systematic method. Such a realization method shows a relation between reversible computing systems and physically reversible systems, and suggests a way to highly miniaturized computing systems.
Keywords: reversible logic element, reversible computing, billiard ball model, rotary element, reversible Turing machine, computation-universality