A 1-Tape 2-Symbol Reversible Turing Machine

The Transactions of the IEICE Volume E72 Issue 3 Page 223-228 published_at 1989-03-25
アクセス数 : 410
ダウンロード数 : 186

今月のアクセス数 : 0
今月のダウンロード数 : 0
File
TransIEICE_E72-3_223.pdf 441 KB 種類 : fulltext
Title ( eng )
A 1-Tape 2-Symbol Reversible Turing Machine
Creator
Shirasaki Akihiko
Yoshifumi Gono
Source Title
The Transactions of the IEICE
Volume E72
Issue 3
Start Page 223
End Page 228
Abstract
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.
Keywords
reversible computing
Turing machine
Language
eng
Resource Type journal article
Publisher
電子情報通信学会
Date of Issued 1989-03-25
Rights
Copyright (c) 1989 IEICE
Publish Type Version of Record
Access Rights open access
Source Identifier
[ISSN] 0913-574X
[NCID] AA10684666
[URI] https://search.ieice.org/bin/summary.php?id=e72-e_3_223&category=E&lang=E&year=1989&abst=
[URI] https://search.ieice.org/