July 19, 2005

Under Erasure

This was mostly written in December, back before I went on hiatus, and polished up last week, when jet-lag had me getting up at four a.m. every day.

One of the commonly-accepted bits of lore in the physics of computation and information is Landauer's principle, named after the late, great Rolf Landauer, who first articulated it in 1961. This states that erasing one bit of information is always an entropy-producing operation, and that the entropy it creates is \( k \ln{2} \), where \( k \) is Boltzmann's constant. At a constant (absolute) temperature \( T \), then, erasing \( n \) bits produces \( kTn \ln{2} \) joules of heat. Landauer's principle says that erasure is not thermodynamically reversible; a further, associated claim is that erasure is the only irreversible computational operation, and that, in particular, measurement can be done reversibly. This would establish a connection between thermodynamic reversibility, and logical invertibility — the ability to recover the inputs to a computation from its outputs, if you want to do so.

As I said, Landauer's principle is a commonly accepted bit of physical lore. Unfortunately, I have recently read two papers by philosophers — Orly Shenker's "Logic and Entropy", and John Norton's "Eaters of the Lotus" — which have managed to convince me that all of the usual arguments for Landauer's principle, starting with those of Landauer himself, are invalid. Both Shenker and Norton sketch out physical mechanisms which can store and erase bits in thermodynamically-reversible ways, or at least ones which are thermodynamically reversible in suitable limits (you may have to erase very slowly). There may be flaws in their proposals — detecting such slips is not my strong suit — but if so they're subtle ones, and I'm pretty sure they're right about the invalidity of the normal arguments. At best what has been established is that certain physical realizations of bit-erasure are thermodynamically irreversible, and their entropy production is at least \( k \ln{2} \). If Shenker and Norton are right (and I'm afraid they are), we have no good reason to believe Landauer's principle is a general truth. Where this leaves us, I have no idea.

(One thing which strikes me about this is that, while Norton and Shenker document what seems to be a widespread error, their implicit explanations for it rest on mistakes of reasoning, particularly confusions about when different sorts of ensembles are appropriate. They find no need to invoke the social or political interests of the physicists. Indeed, it would be absurd to do so; what extra-scientific interest is served by thinking that the minimum dissipation compatible with erasure of a bit is \( k \ln{2} \) rather than zero? While I have no doubt that one could talk coherently and interestingly about the social mechanisms which made Landauer's principle endemic among physicists — which carried the idea from his mind to, among others, mine — those mechanisms would seem to have little ability to explain the content of the principle.)

Update, 20 July: Dave Bacon has a good follow-up post; unlike me, he actually explains the arguments involved.

Update, 22 July: Cris Moore, writing in the comments to Dave Bacon's post, presents what may be a problem for Shenker's reversible eraser. I'd need to think about that very carefully. I'm still persuaded, however, by Shenker and Norton's criticisms of the arguments for of Landauer's principle.

Update, 23 July: A new preprint by Tony Short et al. at the Pittsburgh philosophy of science archive (just down the street!) claims to rescue a "qualitative" form of Landauer's principle. (Presumably they mean that any logically irreversible operation must be dissipative to some degree, if not necessarily the \( k \ln{2} \) formula.) I haven't had a chance to read it yet, and probably won't for a while.

Update, 15 March 2014: Put in proper LaTeX for mathematical expressions. Also, a sort-of follow-up.

Physics

Posted by crshalizi at July 19, 2005 11:59 | permanent link

Three-Toed Sloth:   Hosted, but not endorsed, by the Center for the Study of Complex Systems