Sunday, November 1, 2009

Maxwell's Demon: Computation & Physical Entropy

The second law of thermodynamics states that we cannot decrease the entropy of a closed system on average. This is important because if it would not hold, one could in principle build a "perpetuum mobile" (a machine that generates energy out of thin air). However, this is not a trivial law as we will see in the following. Physicist have repeatedly tried to construct machines (on paper mostly) that would violate the second law. The result of these thought experiments was that information (in the form of abstract sequences of bits) is intricately tied to the notion of physical entropy.

Let's first define entropy of a physical system. The usual definition counts the number of microstates contained in a macrostate. This means that we first have to define the macrostate and this usually involves coarse-graining of the micro-world.
The easiest example is a sequence of T coin-flips. Every sequence has an equal probably to occur, however if we study the space of the number of times heads comes up we can easily see that the entropy of the state N=T/2 is much larger than that of N=T. This is because there is only one unique sequence with N=T but NchooseT sequences of N heads (and this quantity peaks at N=T/2).

For a more realistic physical system let's imagine that we have contained 2N molecules in some volume, N of them are colored white, the remaining N are colored black. Let's divide the space in two imaginary halves and also imagine that the molecules randomly move around (as is realistic). Macrostates are now defined as counting the number of black balls in the left half and the number of white balls in the right half, which we will denote with B(l) and W(r). Again, B(l)=N, W(r)=N has a much lower entropy than B(l=N/2), W(r)=N/2, simply because there are many more ways to accomplish the second macrostate in terms of microstates.

If we use macrostates as the actual microstates themselves, then the entropy will always stay constant because there is exactly 1 microstate state per macrostate. However, if we use coarse-grained macrostates, then the entropy will typically increase, because you will tend to observe macrostates states that are more likely to occur. Thus in the case of the molecules, you will approximately find an equal number of white and black balls in the left and right halves. The second law says that you will not move back from this state to the ordered state of all black balls to the left and all white balls to the right. (There are fluctuations around the average, but with many molecules they are very small and the odds against fluctuating into the completely ordered state or enormous.)

All good so far. But Maxwell invented a "demon" that would build a separating wall between the two halves and control a gate. If a white ball approaches the gate from the left, the demon quickly opens the gate and lets the white ball through. Similarly for a black ball coming from the right (see Figure). The end result is that all black balls end up to the left and all white balls to the right.

So did we break the second law? To start with, the system of the molecules is no longer closed because it now includes the demon. But how will we treat the demon thermodynamically? Our first guess is that the act of moving the gate up and down and measuring the white and black balls as they approach the gate increase the entropy by a significant amount (more than can the demon can decrease the entropy of the environment). Although this is what will usually happen in practice, it turns out that the demon's trick can actually be achieved by a computer with vanishing increase of entropy (of course the construction is subtle, but you will have to take it on faith).

However, the demon will have to obtain information from the system and record it (say on a tape) in order to be able to operate the gate. As it turns out, one can actually decrease the entropy of the molecules in a vat only at the expense of recording the information about the system. Note that we are talking about an abstract sequence of 0's and 1's here. One can show that the act of erasing this information again will necessarily increase the entropy by an amount more then was extracted from the environment in the first place. Again, this is a very subtle argument, because the information needs to be erased irreversibly and that may not be as easy as it looks. Anyway, we will take it for granted now.

This then restores the second law before and after we recorded and erased the information, but what happened in the middle? Did we beat the second law for an arbitrary long time (the time information was recorded on a tape)? In a way yes, and physicist have been forced to change the definition of the second law to include the abstract (Shannon type) information of the sequence of 0's and 1's living on the tape. The new law says that the total entropy of the physical system plus that of the bit-string will not decrease over time. Hence, we have moved some of the entropy of the physical system onto a computer memory and froze it there. The boarders between the real physical world and the abstract world of computer science have been blurred.

This story re-enforces the opinion that physics can be understood as computation ("it from bit" according to Wheeler). But it also points to a potentially deep connection between intelligence (learning systems) and physics. The demon had to study the system and record the information in his "brain" before he could lower the entropy of his environment. But according to a Bayesian, the amount of information obtained by the demon has only meaning relative to his own subjective prior about the world. Is entropy then in the end a subjective quantity? There are many more indications that at least certain aspects about the world are rather subjectively defined (for instance the collapse of the wave function in quantum mechanics leading to the Schrodinger's cat paradox). Is there even an objective world out there? That will have to wait for another blog (;-).