Hacker News Reader

Comment by mjfl | Hacker News Reader

Unfortunately these statistical physics models help about as much as statistical physics models would help in deciphering the x86 instruction set architecture from the activity of the microchip - very little. Too much averaging. Computation is entropy 0 phenomena.

View on HN

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.

> Computation is entropy 0 phenomena.

How do you reconcile that with https://en.wikipedia.org/wiki/Landauer%27s_principle ?

Landauer's principle says that heat is sent into the environment in response erasing bits. entropy is increased in the environment, not the computer.

Reply on news.ycombinator.com