A Universal Reversible Turing Machine that Directly Simulates Reversible Counter Machines

Abstract

We construct a 1-tape 98-state 10-symbol universal reversible Turing machine (URTM(98,10)) that directly simulates reversible counter machines (RCMs). The objective of this construction is not to minimize the numbers of states and tape symbols, but to give a URTM a reasonable size whose simulating processes of RCMs are easily understood. Here, we choose RCMs as the target machines of simulation, since the class of RCMs is known to be Turing universal, and their operations are very simple. Furthermore, using the framework of RCMs in the program form (rather than the quadruple form), construction of a URTM is simplified. We also created a computer simulator for the URTM(98,10), by which simulation processes of RCMs are visualized.

Keywords

• reversible computing
• reversible turing machine
• universal turing machine
• reversible counter machine