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 件
この文献の参照には次のURLをご利用ください : https://ir.lib.hiroshima-u.ac.jp/00048448
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/
|