A 1-Tape 2-Symbol Reversible Turing Machine

Kenichi MORITA; Akihiko SHIRASAKI; Yoshifumi GONO

A 1-Tape 2-Symbol Reversible Turing Machine

Kenichi MORITA, Akihiko SHIRASAKI, Yoshifumi GONO

Full Text Views

0

Share
Cite this

Summary :

Bennett proved that any irreversible Turing machine can be simulated by a 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.

Publication: IEICE TRANSACTIONS on transactions Vol.E72-E No.3 pp.223-228

Publication Date: 1989/03/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Automaton, Language and Theory of Computing

Authors

Kenichi MORITA
Akihiko SHIRASAKI
Yoshifumi GONO

Keyword

Cite this

Copy

Kenichi MORITA, Akihiko SHIRASAKI, Yoshifumi GONO, "A 1-Tape 2-Symbol Reversible Turing Machine" in IEICE TRANSACTIONS on transactions, vol. E72-E, no. 3, pp. 223-228, March 1989, doi: .
Abstract: Bennett proved that any irreversible Turing machine can be simulated by a 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.
URL: https://globals.ieice.org/en_transactions/transactions/10.1587/e72-e_3_223/_p

Copy

@ARTICLE{e72-e_3_223,
author={Kenichi MORITA, Akihiko SHIRASAKI, Yoshifumi GONO, },
journal={IEICE TRANSACTIONS on transactions},
title={A 1-Tape 2-Symbol Reversible Turing Machine},
year={1989},
volume={E72-E},
number={3},
pages={223-228},
abstract={Bennett proved that any irreversible Turing machine can be simulated by a 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.},
keywords={},
doi={},
ISSN={},
month={March},}

Copy

TY - JOUR
TI - A 1-Tape 2-Symbol Reversible Turing Machine
T2 - IEICE TRANSACTIONS on transactions
SP - 223
EP - 228
AU - Kenichi MORITA
AU - Akihiko SHIRASAKI
AU - Yoshifumi GONO
PY - 1989
DO -
JO - IEICE TRANSACTIONS on transactions
SN -
VL - E72-E
IS - 3
JA - IEICE TRANSACTIONS on transactions
Y1 - March 1989
AB - Bennett proved that any irreversible Turing machine can be simulated by a 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.
ER -