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
名前 / ファイル | ライセンス | アクション |
---|---|---|
![]() |
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 |