Reversible Turing Machines and Polynomial Time Reversibly Computable Functions

The reversible Turing machine (i.e., $r$-machine) was introduced initially by C. H. Bennett [IBM J. Res. Develop., 6 (1973), pp. 525-532]. In the first part of the paper a convenient representation of $r$-machines is introduced by means of diagrams. By using this method the following theorem can be...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on discrete mathematics 1990-05, Vol.3 (2), p.241-254
Main Authors: Jacopini, G., Mentrasti, P., Sontacchi, G.
Format: Article
Language:English
Subjects:
Graphs
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The reversible Turing machine (i.e., $r$-machine) was introduced initially by C. H. Bennett [IBM J. Res. Develop., 6 (1973), pp. 525-532]. In the first part of the paper a convenient representation of $r$-machines is introduced by means of diagrams. By using this method the following theorem can be proved: the invertible partial functions are exactly those that can be computed without surplus information by $r$-machines. Therefore the following problem is pointed out: are the invertible functions that can be computed in polynomial time also $r$-computable in polynomial time? In the second part of the work this open question is connected with the problem P = NP and with the problem of the existence of "one-way" bijections.
ISSN:0895-4801
1095-7146
DOI:10.1137/0403020