CoChat
Sign Up
Cited by 3,679Cellular Automata and ApplicationsComputability, Logic, AI AlgorithmsQuantum-Dot Cellular Automata

Logical Reversibility of Computation

Bennett, C. H.·1973·IBM Journal of Research and Development
DOI 10.1147/rd.176.0525
Open this paper in CoChat — free account

Abstract

The usual general-purpose computing automaton (e.g., a Turing machine) is logically irreversible—its transition function lacks a single-valued inverse. Here it is shown that such machines may be made logically reversible at every step, while retaining their simplicity and their ability to do general computations. This result is of great physical interest because it makes plausible the existence of thermodynamically reversible computers which could perform useful computations at useful speed while dissipating considerably less than kT of energy per logical step. In the first stage of its computation the logically reversible automaton parallels the corresponding irreversible automaton, except that it saves all intermediate results, thereby avoiding the irreversible operation of erasure. The second stage consists of printing out the desired output. The third stage then reversibly disposes of all the undesired intermediate results by retracing the steps of the first stage in backward order (a process which is only possible because the first stage has been carried out reversibly), thereby restoring the machine (except for the now-written output tape) to its original condition. The final machine configuration thus contains the desired output and a reconstructed copy of the input, but no other undesired data. The foregoing results are demonstrated explicitly using a type of three-tape Turing machine. The biosynthesis of messenger RNA is discussed as a physical example of reversible computation.

Integrity signals

Registry

Crossref · 10.1147/rd.176.0525

Cites

1 of 1 references verified0 citation errors · 0 not checkable

Statistics

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

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.

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • A general process on a closed system can be described in terms of reversible channels on larger open systems for both quantum and classical theory.

    “It is possible to describe a general process on a closed system in terms of reversible channels on (larger) open systems for both quantum and classical theory [52,53].”

    From Simple formulation of no-cloning and no-hiding that admits efficient and robust verification (2024) · cites this paper as [53]

  • Reversible classical channels are fully generated by the set of isometries and auxiliary classical randomness, as they correspond to injective Boolean functions.

    “Furthermore, reversible classical channels are fully generated by the set of isometries and auxiliary classical randomness [53,55,56], as they correspond to injective Boolean functions.”

    From Simple formulation of no-cloning and no-hiding that admits efficient and robust verification (2024) · cites this paper as [53]

  • In quantum theory, global isometries suffice (captured by Stinespring dilation); classical theory requires the use of auxiliary randomness.

    “In quantum theory, global isometries suffice (captured by a Stinespring dilation [54]); however, classical theory requires the use of auxiliary randomness [53].”

    From Simple formulation of no-cloning and no-hiding that admits efficient and robust verification (2024) · cites this paper as [53]

  • In the special case where f can be efficiently computed deterministically, it is easy to design the subroutine so that it reversibly erases the scratch-work by computing f(x), copying f(x) into safe storage, and then uncomputing f(x).

    “In the special case where f can be efficiently computed deterministically, it is easy to design the subroutine so that it reversibly erases the scratch-work-simply compute f ( x ), copy f ( x ) into safe storage, and then uncompute f ( x ) to get rid of the scratch work [2].”

    From Strengths and Weaknesses of Quantum Computing (1997) · cites this paper as [2]

  • Any computation can be performed reversibly both logically and thermodynamically, in principle by a physical apparatus dissipating arbitrarily little energy.

    “It is possible to perform any computation in a way that is reversible both logically -i.e., the computation is a sequence of bijective transformations-and thermodynamically -the computation could in principle be performed by a physical apparatus dissipating arbitrarily little energy [2].”

    From Elementary gates for quantum computation (1995) · cites this paper as [2]

Cites

Flagged first, then by citations

Cited by

Sorted by citations

Related

Authors
Bennett, C. H.
Affiliations
IBM Research - Thomas J. Watson Research Center (US)
Corresponding author
Bennett, C. H.
Venue
IBM Journal of Research and Development
Publisher
IBM
Published
1973-11
Volume
17
Issue
6
Pages
525-532
ISSN
0018-8646 (ISSN-L)
DOI
10.1147/rd.176.0525
OpenAlex
W2105259569
Cited by
3,679
References
1
Citations by year
2026: 106 · 2025: 118 · 2024: 116 · 2023: 159 · 2022: 156 · 2021: 147 · 2020: 166 · 2019: 141 · 2018: 164 · 2017: 192 · 2016: 193 · 2015: 178 · 2014: 221 · 2013: 168 · 2012: 156
FWCI
5.23
Type
journal article
Language
en
Open access
closed
Locations
IBM Journal of Research and Development (publishedVersion)
Topics
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Cellular Automata and Applications
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Computability, Logic, AI Algorithms
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Quantum-Dot Cellular Automata
Keywords
logical reversibility, reversible computation, Turing machines, information erasure, energy dissipation

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