WEKO3
アイテム
A 1-Tape 2-Symbol Reversible Turing Machine
https://hiroshima.repo.nii.ac.jp/records/2008958
https://hiroshima.repo.nii.ac.jp/records/20089587f71285f-827d-4ba1-8056-4fc3cde97f28
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
TransIEICE_E72-3_223.pdf (440.9 KB)
|
| Item type | デフォルトアイテムタイプ_（フル）(1) | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2023-03-18 | |||||||||||
| タイトル | ||||||||||||
| タイトル | A 1-Tape 2-Symbol Reversible Turing Machine | |||||||||||
| 言語 | en | |||||||||||
| 作成者 |
Morita, Kenichi
× Morita, Kenichi
× Shirasaki, Akihiko
× Yoshifumi, Gono
|
|||||||||||
| アクセス権 | ||||||||||||
| アクセス権 | open access | |||||||||||
| アクセス権URI | http://purl.org/coar/access_right/c_abf2 | |||||||||||
| 権利情報 | ||||||||||||
| 権利情報 | Copyright (c) 1989 IEICE | |||||||||||
| 主題 | ||||||||||||
| 主題Scheme | Other | |||||||||||
| 主題 | reversible computing | |||||||||||
| 主題 | ||||||||||||
| 主題Scheme | Other | |||||||||||
| 主題 | Turing machine | |||||||||||
| 内容記述 | ||||||||||||
| 内容記述 | 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. | |||||||||||
| 言語 | en | |||||||||||
| 出版者 | ||||||||||||
| 出版者 | 電子情報通信学会 | |||||||||||
| 言語 | ||||||||||||
| 言語 | eng | |||||||||||
| 資源タイプ | ||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||||
| 資源タイプ | journal article | |||||||||||
| 出版タイプ | ||||||||||||
| 出版タイプ | VoR | |||||||||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||||||||
| 関連情報 | ||||||||||||
| 識別子タイプ | 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/ | |||||||||||
| 収録物識別子 | ||||||||||||
| 収録物識別子タイプ | ISSN | |||||||||||
| 収録物識別子 | 0913-574X | |||||||||||
| 収録物識別子 | ||||||||||||
| 収録物識別子タイプ | NCID | |||||||||||
| 収録物識別子 | AA10684666 | |||||||||||
| 開始ページ | ||||||||||||
| 開始ページ | 223 | |||||||||||
| 書誌情報 |
The Transactions of the IEICE The Transactions of the IEICE 巻 E72, 号 3, p. 223-228, 発行日 1989-03-25 |
|||||||||||
| 旧ID | 48448 | |||||||||||
