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
アクセス数 : 411 件
ダウンロード数 : 186 件
今月のアクセス数 : 1 件
今月のダウンロード数 : 0 件
この文献の参照には次のURLをご利用ください : https://ir.lib.hiroshima-u.ac.jp/00048448
| File | |
| 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/
|
