Constructing Reversible Turing Machines in a Reversible and Conservative Elementary Triangular Cellular Automaton
Kenichi Morita · Journal of automata, languages and combinatorics · 2021
We study the problem of how we can construct reversible Turing machines (RTMs) compactly in a two-dimensional reversible cellular automaton (CA). The CA model used here is an elementary triangular partitioned CA (ETPCA) having an extremely simple local transition function. It has been shown that any RTM is realized in a reversible and non-conservative ETPCA No. 0347, where 0347 is an identification number in the class of 256 ETPCAs. In this paper, we show that it is also possible to construct RTMs in a reversible and conservative ETPCA 0137, which has very different features from ETPCA 0347, by a systematic and hierarchical manner. Here, a reversible logic element with memory (RLEM), rather than a reversible logic gate, is used in the basic level of the construction. In particular, a special type of an RLEM No. 4-31 is implemented in ETPCA 0137. Then RTMs are constructed using the RLEM pattern. By this, the construction of configurations that simulates RTMs is greatly simplified.