CoChat
Sign Up
Cited by 405Computability, Logic, AI Algorithmssemigroups and automata theoryComplexity and Algorithms in Graphs

The DOI matches its Crossref record; 12 of the 12 references it cites were found in a registry or an index.

Time/Space Trade-Offs for Reversible Computation

Bennett, Charles H.·1989·SIAM Journal on Computing
DOI 10.1137/0218053
Open this paper in CoChat — free account

Abstract

A reversible Turing machine is one whose transition function is $1:1$, so that no instantaneous description (ID) has more than one predecessor. Using a pebbling argument, this paper shows that, for any $\varepsilon > 0$, ordinary multitape Turing machines using time T and space S can be simulated by reversible ones using time $O(T^{1 + \varepsilon } )$ and space $O(S\log T)$ or in linear time and space $O(ST^\varepsilon )$. The former result implies in particular that reversible machines can simulate ordinary ones in quadratic space. These results refer to reversible machines that save their input, thereby insuring a global $1:1$ relation between initial and final IDs, even when the function being computed is many-to-one. Reversible machines that instead erase their input can of course compute only $1:1$ partial recursive functions and indeed provide a Godel numbering of such functions. The time/space cost of computing a $1:1$ function on such a machine is equal within a small polynomial to the cost of computing the function and its inverse on an ordinary Turing machine.

Overview

Integrity signals

Registry

Crossref · 10.1137/0218053

Cites

12 of 12 references verified0 citation errors · 0 not checkable

Statistics

Recomputing p-values needs the paper’s full text.

Verification

Claims the paper makes

This paper’s full text isn’t openly available, so its claims and self-check weren’t run. The registry and citation checks still apply.

Citations

Cites

Show all 12 references

Research works printed but not linked: 3

  1. R. Cleve, Ph.D. Thesis, Methodologies for designing block ciphers and cryptographic protocols, Computer Science Department, University of Toronto, Toronto, Ontario, Canada, 1988
  2. Levin L., 1973, Problems Inform. Transmission, 10, 206
  3. T. Toffoli, Reversible computing, MIT Report, MIT/LCS/TM-151, Mass. Inst. of Technology, Cambridge, MA, 1980 · DOI · Paper page

Cited by

Sorted by citations

Related

See all

Metadata

Authors
Bennett, C. H.
Affiliations
IBM Research - Thomas J. Watson Research Center (US)
Corresponding author
Bennett, Charles H.
ORCID
Bennett, Charles H.
Venue
SIAM Journal on Computing
Publisher
Society for Industrial & Applied Mathematics (SIAM)
Published
1989-08
Volume
18
Issue
4
Pages
766-776
ISSN
  • 0097-5397 (ISSN-L)
  • 1095-7111
DOI
10.1137/0218053
OpenAlex
W2061073612
Cited by
405
References
12
Citations by year
2026: 11 · 2025: 20 · 2024: 13 · 2023: 10 · 2022: 18 · 2021: 24 · 2020: 26 · 2019: 15 · 2018: 21 · 2017: 16 · 2016: 43 · 2015: 14 · 2014: 5 · 2013: 6 · 2012: 6
FWCI
2.52
Type
journal article
Language
en
Open access
closed
Locations
SIAM Journal on Computing (publishedVersion)
Topics
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Computability, Logic, AI Algorithms
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › semigroups and automata theory
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
Keywords
reversible computation, reversible Turing machines, space-time tradeoff, pebbling, multitape Turing machines, one-to-one functions, partial recursive functions, inverse functions, space complexity, time complexity

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review