A 1-Tape 2-Symbol Reversible Turing Machine
The Transactions of the IEICE E72 巻 3 号
223-228 頁
1989-03-25 発行
アクセス数 : 386 件
ダウンロード数 : 174 件
今月のアクセス数 : 3 件
今月のダウンロード数 : 4 件
この文献の参照には次のURLをご利用ください : https://ir.lib.hiroshima-u.ac.jp/00048448
| ファイル情報(添付) | |
| タイトル ( eng ) |
A 1-Tape 2-Symbol Reversible Turing Machine
|
| 作成者 |
Shirasaki Akihiko
Yoshifumi Gono
|
| 収録物名 |
The Transactions of the IEICE
|
| 巻 | E72 |
| 号 | 3 |
| 開始ページ | 223 |
| 終了ページ | 228 |
| 抄録 |
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.
|
| 著者キーワード |
reversible computing
Turing machine
|
| 言語 |
英語
|
| 資源タイプ | 学術雑誌論文 |
| 出版者 |
電子情報通信学会
|
| 発行日 | 1989-03-25 |
| 権利情報 |
Copyright (c) 1989 IEICE
|
| 出版タイプ | Version of Record（出版社版。早期公開を含む） |
| アクセス権 | オープンアクセス |
| 収録物識別子 |
[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/
|
