Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question

migrated from cstheory.stackexchange.com Mar 13 at 5:41

This question came from our site for theoretical computer scientists and researchers in related fields.

add comment

1 Answer 1

up vote 11 down vote accepted

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.

share|improve this answer
    
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? –  Eli Rose Mar 13 at 6:27
2  
@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. –  Artem Kaznatcheev Mar 13 at 6:40
1  
@ArtemKaznatcheev: what about Reversible Turing Machines (PDF link) introduced by Bennett? –  Niel de Beaudrap Mar 13 at 7:36
    
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. –  supercat Mar 13 at 18:04
    
what about quantum TMs whose allowed amplitudes can only be 0 or 1. That seems a reasonable way to define a reversible TM. –  Marcos Villagra Mar 14 at 15:30
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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