5 ms·

In theory yes, the catch is that you're not allowed to forget information. For instance, you cannot use an "AND" gate, because a result of 0 would be ambiguous,

In theory yes, the catch is that you're not allowed to forget information. For instance, you cannot use an "AND" gate, because a result of 0 would be ambiguous, but you can use the Toffoli gate [1] which takes three inputs and produces three outputs, mapping (a,b,c) to (a,b,c^(a&b)). But what happens to the outputs you don't need? They do need to go somehere. A reversible circuit ends up having a lot of unused outputs which need to be erased if the circuit is to be reused. In essence, we have traded a heatsink for a bitsink, but they are essentially the same thing. I don't see reversible computing as categorically different from regular computing. It's regular computing, with careful and detailed heat management. [1] https://en.wikipedia.org/wiki/Toffoli_gate https://en.wikipedia.org/wiki/Toffoli_gate

std_throwaway 10y ago
Couldn't you just uncompute instead of erasing to restore the ground state before computing something else? To my understanding you just need energy to set the inputs, give it a little push and everything else runs on its own (forwards and backwards).
- murbard2 10y ago
  You can uncompute, but in that case you need to erase the input to replace it with a new input.
- DonHopkins 10y ago
  There's a Philip K Dick book about that. (For any sufficiently weird idea, there usually is.) Counter Clock World The most powerful -- and most feared -- organisation in the world is the Library, in charge of expunging the written records of events, which have no longer happened. https://en.wikipedia.org/wiki/Counter-Clock_World https://en.wikipedia.org/wiki/Counter-Clock_World The novel describes a future in which time has started to move in reverse, resulting in the dead reviving in their own graves ("old-birth"), living their lives in reverse, and eventually returning to the womb where they split into an egg and a sperm during copulation between a recipient woman and a man. The Hobart Phase The Hobart Phase is the new order of life where people rise from the dead and are rejuvenated. Time reversal apparently began in 1986. Other than aging, Hobart Phase resurrection has changed nutritional and excretion processes and associated social taboos. People do not eat, but instead consume "Sogum" anally through a pipe, and later "plop" out food orally, which is done in private, due to its 'shameful' nature. As for smoking, cigarettes are no longer smoked, but the smoke instead blown back into them, making them grow back to normal size (this also clears and freshens the air). "Goodbye" and "hello" have reversed their order within standard greetings, and "food" is used as a drop-in replacement for the expletive "shit". It is stated that Mars colonists do not have the Hobart Phase on their world, and it is limited to Earth, and presumably its lunar colonies as well.
_0ffh 10y ago
I wonder if the "bitsink instead of heatsink" problem might be somewhat mitigable. So, we are just pushing our 0s and 1s around, instead of permanently destroying and re-creating them. As reversible logic is as universal as, say, NAND logic - wouldn't it be possible to sort the unused output bits of any gates into two pools for 0s and 1s [1] and use these pools for any constant inputs that are needed in the logic? So that we would only have to "create" any new 0s and 1s when one of these two pools runs dry? [1] E.g. a sorting buffer with 0s at one end and 1s at the other. Or does sorting necessarily mean we are sorting unknown bits at the cost of mixing known bits (constant gate inputs)?
- murbard2 10y ago
  If you sort two bits and get 0, 1 you can't know if you started out with 0, 1 or 1, 0. The entropy of a sorted list of bit is O(log(n)) while the entropy of the unsorted bits is O(n).
- placeybordeaux 10y ago
  Sorting loses information proportional to the size of the list you are sorting.
- hcs 10y ago
  Sorting is not reversible, at least if your output is no larger than your input. [0,1] and [1,0] both sort to [0,1], so you'd already need 1 extra bit to unsort 2 bits. I don't see how it would help anyway, but maybe I'm misunderstanding your suggestion. The state of these unwanted outputs needs to be kept around, if you know they will be 0 or 1 then the state is already implicit in the machine and the output isn't actually necessary.
- _0ffh 10y ago
  [Self reply because this more or less concerns all replies to parent I have seen so far.] "sorting is not reversible"/"you can't know [the original order]"/"sorting loses information" These replies are have two problems in common: 1. They are wrong in the context of reversible gates, because (as I have hinted in my comment) when you sort bits using a normal reversible gate, then the original order of the bits will be encoded in the unused gate outputs. No information is lost, that's why we call these gates reversible in the first place. 2. The heart of my speculation lies in the question if a special irreversible circuit could be integrated into a reversible CPU, which moves bits into order without unnecessarily grounding charges. The more I think about it, the more I tend to think it could. Edit: To make a clearer point on where I'm coming from here: I view reversibility not as a goal in itself, but a tool to use to get ultra low power compute capabilities. To achieve this, the unused output charges need to be recycled into the system. If you solve that problem, you have achieved the goal.

std_throwaway 10y ago

Couldn't you just uncompute instead of erasing to restore the ground state before computing something else? To my understanding you just need energy to set the inputs, give it a little push and everything else runs on its own (forwards and backwards).

murbard2 10y ago
You can uncompute, but in that case you need to erase the input to replace it with a new input.
DonHopkins 10y ago
There's a Philip K Dick book about that. (For any sufficiently weird idea, there usually is.) Counter Clock World The most powerful -- and most feared -- organisation in the world is the Library, in charge of expunging the written records of events, which have no longer happened. https://en.wikipedia.org/wiki/Counter-Clock_World https://en.wikipedia.org/wiki/Counter-Clock_World The novel describes a future in which time has started to move in reverse, resulting in the dead reviving in their own graves ("old-birth"), living their lives in reverse, and eventually returning to the womb where they split into an egg and a sperm during copulation between a recipient woman and a man. The Hobart Phase The Hobart Phase is the new order of life where people rise from the dead and are rejuvenated. Time reversal apparently began in 1986. Other than aging, Hobart Phase resurrection has changed nutritional and excretion processes and associated social taboos. People do not eat, but instead consume "Sogum" anally through a pipe, and later "plop" out food orally, which is done in private, due to its 'shameful' nature. As for smoking, cigarettes are no longer smoked, but the smoke instead blown back into them, making them grow back to normal size (this also clears and freshens the air). "Goodbye" and "hello" have reversed their order within standard greetings, and "food" is used as a drop-in replacement for the expletive "shit". It is stated that Mars colonists do not have the Hobart Phase on their world, and it is limited to Earth, and presumably its lunar colonies as well.

_0ffh 10y ago

I wonder if the "bitsink instead of heatsink" problem might be somewhat mitigable. So, we are just pushing our 0s and 1s around, instead of permanently destroying and re-creating them. As reversible logic is as universal as, say, NAND logic - wouldn't it be possible to sort the unused output bits of any gates into two pools for 0s and 1s [1] and use these pools for any constant inputs that are needed in the logic? So that we would only have to "create" any new 0s and 1s when one of these two pools runs dry? [1] E.g. a sorting buffer with 0s at one end and 1s at the other. Or does sorting necessarily mean we are sorting unknown bits at the cost of mixing known bits (constant gate inputs)?

murbard2 10y ago
If you sort two bits and get 0, 1 you can't know if you started out with 0, 1 or 1, 0. The entropy of a sorted list of bit is O(log(n)) while the entropy of the unsorted bits is O(n).
placeybordeaux 10y ago
Sorting loses information proportional to the size of the list you are sorting.
hcs 10y ago
Sorting is not reversible, at least if your output is no larger than your input. [0,1] and [1,0] both sort to [0,1], so you'd already need 1 extra bit to unsort 2 bits. I don't see how it would help anyway, but maybe I'm misunderstanding your suggestion. The state of these unwanted outputs needs to be kept around, if you know they will be 0 or 1 then the state is already implicit in the machine and the output isn't actually necessary.
_0ffh 10y ago
[Self reply because this more or less concerns all replies to parent I have seen so far.] "sorting is not reversible"/"you can't know [the original order]"/"sorting loses information" These replies are have two problems in common: 1. They are wrong in the context of reversible gates, because (as I have hinted in my comment) when you sort bits using a normal reversible gate, then the original order of the bits will be encoded in the unused gate outputs. No information is lost, that's why we call these gates reversible in the first place. 2. The heart of my speculation lies in the question if a special irreversible circuit could be integrated into a reversible CPU, which moves bits into order without unnecessarily grounding charges. The more I think about it, the more I tend to think it could. Edit: To make a clearer point on where I'm coming from here: I view reversibility not as a goal in itself, but a tool to use to get ultra low power compute capabilities. To achieve this, the unused output charges need to be recycled into the system. If you solve that problem, you have achieved the goal.