I'm an undergraduate just beginning to read about reversible computing. I know that, because of Landauer's principle, irreversible computations dissipate heat (and reversible ones do not). I brought it up with my professor, who had never heard of reversible computing before, and he was having difficulty understanding why the theory of reversible computing was not trivial.

His point was just that you can always save the input, i.e. for any function $f: \{ 0, 1 \}^n \rightarrow \{ 0, 1 \}^n$ that you wish to make reversible, define a new function $f_{reversible}: \{ 0, 1 \}^n \rightarrow \{0, 1 \}^{2n}$ (or $\{ 0, 1 \}^{2n} \rightarrow \{0, 1 \}^{2n}$ and you just put $0$s in for the last $n$ bits of the input) which returns the output in the first $n$ bits and the input in the other $n$ bits. Then in order to invert $f_{reversible}$ you just discard the output and return the input that you saved.

My immediate objection was that this takes more memory than the original function did -- though only by a constant factor. Constraining the output to $n$ bits would seem to restore the interesting-ness of the problem, though. Is this what is usually meant by reversible computing?

Another objection seemed to be that when we discard the output, we're doing something irreversible which is going to dissipate heat. But we correctly recovered the initial state, so how could it be irreversible? I don't know enough physics to understand whether the important thing w/r/t heat is just for the entire computation to be reversible, or whether every step needs to be reversible as well, or if this idea is just up the wrong tree.


1 Answer 1


There are two important features of reversible computing that are missing from your discussion of reversible computing:

  1. A reversible function has to be a bijection, and
  2. Reversibility is defined on the level of local gates, not just the global level.

In particular, for your extension of $\{0,1\}^n \rightarrow \{0,1\}^n$ into $\{0,1\}^{2n} \rightarrow \{0,1\}^{2n}$ by copying, you don't ensure bijection because you don't explain what happens when the last $n$ bits of input for your function aren't $0^n$.

As for the second point, that is really the essential part of reversible-computing from the physics perspective. The physical process can't simply "undo" heating at a global level, thus every gate has to be reversible for the circuit to be reversible in the relevant-to-physics sense.

Finally, the theory of reversible computing is not unreasonably complicated, but it is definitely not trivial. In particular, there are some circuits that can be implemented with strictly fewer registers/wires non-reversibly than they can be reversibly. However, the blow up in going from non-reversible to reversible is not too bad.

In general, I seldom hear reversible computing come up in classical CS courses, because it is seldom relevant to classical computation. However, it is an important topic in quantum computing because all quantum circuits are reversible and because one has to handle what is on your 'junk' wires carefully to avoid unnecessary entanglement.

  • $\begingroup$ Aha. So what's the formal statement of "every gate has to be reversible" -- is it requiring the transition function of the Turing machine to be injective? $\endgroup$
    – Eli Rose
    Mar 13, 2014 at 6:27
  • 2
    $\begingroup$ @EliRose reversible computing is defined in the gate model, not the TM model. I am not sure if there is a reasonable definition in the TM model, but it would probably at least require the finite control to be reversible. So reversible gates means something like the Toffoli gate. $\endgroup$ Mar 13, 2014 at 6:40
  • 1
    $\begingroup$ @ArtemKaznatcheev: what about Reversible Turing Machines (PDF link) introduced by Bennett? $\endgroup$ Mar 13, 2014 at 7:36
  • $\begingroup$ Combinatorial circuits can easily be handled with reversible logic, but all useful computing devices require feedback. One could use a Toffoli gate to compute "A and not B", and two such gates could be used to build a latch, but once the feedback is put in place, reversibility goes out the window. $\endgroup$
    – supercat
    Mar 13, 2014 at 18:04
  • $\begingroup$ what about quantum TMs whose allowed amplitudes can only be 0 or 1. That seems a reasonable way to define a reversible TM. $\endgroup$ Mar 14, 2014 at 15:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.