# Reversible Computation and Freeing Memory

Discussion in 'Computer Science & Culture' started by MrMormon, Sep 24, 2011.

Not open for further replies.
1. ### MrMormonRegistered Senior Member

Messages:
73
What's the concern with a complex system? The only concern is reducing heat generated near the main processor(s).

I'm not sure you understand garbage bits - memory is 'filled' because the unneeded bits of every reversible operation are preserved, and gates are part of computing, not memory. You can't just shift around and keep the garbage bits forever, because information is always increasing with input into the computer.

3. ### arfa branecall me arfValued Senior Member

Messages:
7,637
Here's the wiki on Landauer's principle (note: "the erasure problem" appears to be an adapted terminology, I think Bennet uses it though)

"Landauer's Principle, first argued in 1961[1] by Rolf Landauer of IBM, holds that "any logically irreversible manipulation of information, such as the erasure of a bit or the merging of two computation paths, must be accompanied by a corresponding entropy increase in non-information bearing degrees of freedom of the information processing apparatus or its environment". (Bennett 2003)[2].

The Landauer's Principle describes the Landauer limit, which is the minimum possible amount of energy required to change one bit of information, as follows:

kT · ln 2

Where…
k is the Boltzmann constant
T is the absolute temperature of the circuit in kelvins
ln 2 is the natural logarithm of 2, which is approximately 0.69315

At 25 °C (room temperature, or 298.15 kelvins), the Landauer limit represents an energy of approximately 0.0178 electron volt. Theoretically, room‑temperature computer memory operating at the Landauer limit could be changed at a rate of one billion bits per second with only 2.85 trillionths of a watt of power being expended in the memory media.

If no information is erased, computation may in principle be achieved which is thermodynamically reversible, and require no release of heat. This has led to considerable interest in the study of reversible computing."

5. ### MrMormonRegistered Senior Member

Messages:
73
I can imagine a computer with several TB of RAM that can run with no heat for a long time, but eventually one would have to stop using it for a little while to let it erase garbage bits so that it can be reused. Still, not ideal.

7. ### arfa branecall me arfValued Senior Member

Messages:
7,637
But if you build a computer with "sufficient" gates that a separate memory isn't needed, that is, you use every gate once and "keep the inputs" then the inputs are equivalent to memory, the computer "remembers" all the inputs for a computation.

Modern digital computers do use gates more than once, hence the outputs of gates are stored in a separate set of memory registers, but the memory is also reused, hence "the erasure problem" and heat that has to dissipate (equivalent to the information which is erased according to Landauer's principle).

Then a computer with no separate memory and a large enough number of gates can perform a reversible computation, as long as none of the inputs corresponding to any computation are erased or dissipated. Then there aren't any garbage bits.

8. ### MrMormonRegistered Senior Member

Messages:
73
It's true that one doesn't need intermediate memory with the right combination of gates to implement any finite algorithm, but most computers aren't just used for running algorithms like supercomputers. Much more importantly, I don't think configurable reversible circuits would be as fast as static ones. Look at FPGAs.

9. ### arfa branecall me arfValued Senior Member

Messages:
7,637
But aren't we discussing reversible computation? The "right combination" is logic gates whose outputs include some (or all) of their inputs so that logical reversibility (by computing the inputs from the outputs) is possible.

10. ### MrMormonRegistered Senior Member

Messages:
73
Yes, but individually. Gates modify memory - they aren't memory.

Also, why aren't others commenting too?

11. ### arfa branecall me arfValued Senior Member

Messages:
7,637
I think you misunderstand. If say a 2-input gate doesn't change either input and computes an output, then it remembers the inputs.

So maintaining inputs is the same thing as storing their states in memory. All you need to do is make the inputs into outputs and you have the equivalent of memory--as long as the inputs don't change.

In other words, if you use each gate once only, and pass the inputs through to another gate you use at some later time to compute reversibly. Which means, recover the inputs from all the outputs. This is exactly what Toffoli and Fredkin gates do.

12. ### MrMormonRegistered Senior Member

Messages:
73
It sounds like you're proposing flash memory or something else that can only maintain a state as long as the computer is running.

13. ### arfa branecall me arfValued Senior Member

Messages:
7,637
It sounds like you don't actually understand the subject of reversible computing.

Do you know what a 3-input/3-output gate is, and why anyone would bother to design one?
Do you understand why your idea means you would need a fairly complex memory system, and why it would restrict the speed of a reversible computer if it had to erase information? So there wouldn't be any overall improvement in computational efficiency, unless the memory was large enough that information wasn't erased, in which case the circuit controlling the memory would be at least as complex, if not more complex, than the rest of the computer?

Which means, your idea hasn't been implemented because it isn't practical?

Sorry, but I think this thread isn't really going anywhere.

14. ### MrMormonRegistered Senior Member

Messages:
73
A complex memory system may or may not be a bottleneck. I agree that this conversation is going nowhere, especially since no one else is commenting...

15. ### arfa branecall me arfValued Senior Member

Messages:
7,637
Yeah. And I was getting bored with repeating myself, too.

16. ### MrMormonRegistered Senior Member

Messages:
73
I felt the same way. We're even.

Thanks for talking, though.

17. ### funkstarratsknufValued Senior Member

Messages:
1,390
Ok, I didn't notice this thread earlier, or I would have replied.

I'd like to comment on one aspect. You both seem to think (please correct me if I'm wrong) that using reversible gates necessarily means that inputs of each individual gate must be conserved, and that they are no longer useful once the gate has been applied. This is not the case, and a large part of coming up with good reversible (and quantum) logic design is finding ways to use the other outputs as well. Indeed, it is perfectly possible to make reversible logic designs where only a tiny number of the input lines (as summed over the number of gates) is conserved.

For example, here's a ripple-carry adder which maps (a,b) to (a,a+b)), with a single ancillae bit, and no "garbage" bits. Note that not all inputs are conserved. This means that you can restrict the growth of "garbage information".

18. ### arfa branecall me arfValued Senior Member

Messages:
7,637
No, using reversible logic means restoring the initial inputs. So you need to keep enough information around to do this. With the logical OR operation on two inputs, it's possible to restore both input states reliably from the output and one (initial) input.

[ed: oops, actually that's only true of XOR with two-input gates. That's why three-input gates are a better choice, apart from being able to configure such gates by using one or two inputs to control the gate's function.]

So you need an OR gate that preserves one of its inputs. Inversion is obviously logically reversible. That leaves Boolean AND, which can only be logically reversible if both the initial inputs are preserved. AND logic is not affine (it can't be expressed as a linear transformation of its inputs), which is why Boolean logic is not universal.

Last edited: Oct 11, 2011
19. ### MrMormonRegistered Senior Member

Messages:
73
In addition (no pun intended), mapping (a,b) to (a,a+b) should be entirely reversible. If you have another example though, that would be great.

20. ### funkstarratsknufValued Senior Member

Messages:
1,390
It doesn't have to. The reversible adder I linked to doesn't, for example: it only conserves one of its two n-bit inputs.
I'm not sure I understand your meaning. I explicitly mentioned it as a reversible example.

21. ### arfa branecall me arfValued Senior Member

Messages:
7,637
You mean, it only conserves or keeps enough of the input information that it can restore all of it?
Isn't that what I've said a number of times?

Anyway, this from the wiki on Toffoli gates:

22. ### MrMormonRegistered Senior Member

Messages:
73
I didn't really understand, but I thought your example was trying to demonstrate that 'garbage' bits can be reused. If they can't, then the problem of erasure still hasn't been solved at all.

23. ### funkstarratsknufValued Senior Member

Messages:
1,390
That was pretty much it, yes. You can do more complicated things as well, like reversible ALUs.