このエントリーをはてなブックマークに追加
ID 48448
file
creator
Shirasaki, Akihiko
Yoshifumi, Gono
subject
reversible computing
Turing machine
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.
journal title
The Transactions of the IEICE
volume
Volume E72
issue
Issue 3
start page
223
end page
228
date of issued
1989-03-25
publisher
電子情報通信学会
issn
0913-574X
ncid
language
eng
nii type
Journal Article
HU type
Journal Articles
DCMI type
text
format
application/pdf
text version
publisher
rights
Copyright (c) 1989 IEICE
relation url
department
Graduate School of Engineering