Making Reversible Computing Machines in a Reversible Cellular Space

Abstract

Reversible computing is a study that investigates the problem of how computing is effectively performed in a reversible world. Since physical reversibility is one of the fundamental microscopic laws of nature, it is im- portant to clarify how computing machines are realized utilizing a reversible law directly. In this survey/tutorial paper, we investigate this problem using a reversible cellular automaton as a reversible environment, and search for a new way of constructing reversible Turing machines (RTMs), a model of a reversible computer, in it. That is to find a good pathway from a reversible microscopic law to reversible computers. When doing so, it is convenient to assume several conceptual levels on the pathway, by which the problem is decomposed into subproblems. In the middle level on the pathway we use a reversible logic element with 1-bit memory (RLEM), rather than a re- versible logic gate, as a logical primitive. By these methods, we see that RTMs can be implemented systematically even in a space that obeys a very simple reversible microscopic law.