Authors: Kenichi Morita
Keywords: reversible computing, reversible Turing machine, universal Turing machine, reversible counter machine
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.
DOI
https://doi.org/10.56415/csjm.v32.22
Fulltext
–
0.36 Mb