3 ms·

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 destroy

by _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.

by _0ffh 10y ago

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.