A 1-Tape 2-Symbol Reversible Turing Machine
Kenichi Morita, Akihiko Shirasaki, Yoshifumi Gono · Institutional Repositories DataBase (IRDB) · 1989
Bennett proved that any irreversible Turing machine can be simulated by reversible one. However, Bennett's reversible machine uses 3 tapes and many tape symbols. Previously, Gono and Morita showed that the number of symbols can be reduced to 2. In this paper, by improving these methods, we give a procedure to convert an irreversible machine into an equivalent 1-tape 2-symbol reversible machine. First, it is shown that the "state-degeneration degree" of any Turing machine can be reduced to 2 or less. Using this result and some other techniques, a given irreversible machine is converted into a 1-tape 32-symbol (i.e., 5-track 2-symbol) reversible machine. Finally the 32-symbol machine is converted into a 1-tape 2-symbol reversible machine. From this result, it is seen that a 1-tape 2-symbol reversible Turing machine is computation universal.