Comment by tnecniv | Hacker News Reader

Comment by tnecniv | Hacker News Reader

Parent Full thread

As someone posted Landauer’s principle, I’m going to elaborate. Computation is not zero entropy as many operations (the classic example is erasing memory, which you can think about as filling a buffer with a constant) is not invertible. You are mapping memory from holding any value to a constant. Given memory filled with that constant, you can’t undo that deletion unless you have a copy saved somewhere else (in which case the inverse requires extra knowledge than just the state of the memory).

This is also true for many more useful computations: OR and XOR and modulo are not invertible because they map many possible inputs to the same value.

Thus, if you have a distribution over inputs to your algorithm, the distribution over outputs cannot have more entropy and typically will have less.

Small nitpick, XOR is invertible when parameterized by either of its inputs, whereas OR and MOD are not in general.

I.e., (x,y) -> (x,xor(x,y)) is invertible, but (x,y) -> (x,or(x,y)) is not for arbitrary x,y and neither are (x,y) -> (x,mod(x,y)) or (x,y) -> (mod(x,y),y).

Oh that’s interesting and a good point

(x,y) -> (x,xor(x,y)) is usually called CNOT.

The implementation of many types of computation are not 0 entropy, but it’s just an implementation detail. Sure, if you truly want to erase memory, then you can’t do that without an entropy cost. But if your goal is to store information X for use in computation, then you can conceive of a reversible way to do that, or at least conclude that such a reversible process may not be impossible. In this way, Landauer’s limit is a sleight of hand. The conditions under which it is true does not encompass all possible conditions.

The disproofs of Landauer’s limit I am familiar with concern protocols that are not physically realizable, I.e. they require infinite time or an instantaneous quenching step. Do you have a reference that shows you can beat the limit without those assumptions? I’d really like to see how it’s done.

I don't have any proof that it's possible. I'm just saying that it's conceivable that it may be possible. As motivation, consider a quantum computer, where the vast majority of computation done is reversible.

with laundauers phenomenon, the heat (and entroy) is exported to the environment, and is not retained in the computer.

Reply on news.ycombinator.com