A few links

I've been at ICDE in Cancun for the last few days because of this, and it's hard to blog too much from "the best beach in Mexico". There are some interesting trends emerging from this conference, many of which might be interesting to algorithms folks, and I'll try to say more about this later on.

Two links that came across Google Reader and might be of interest:

• "Shut up and calculate", by Max Tegmark (via Mathematics under the Microscope). Tegmark argues for an extreme Platonic position: not only is the universe governed by mathematics, but that it is mathematics ! There's more to this argument in the (short) paper: buried in there is an interesting robust variant of falsificationism:

  For a theory to be falsifiable, we need not be able to observe and test all its predictions, merely at least one of them

• Via BB, New Scientist's list of the ten weirdest computing models (for actual computing, that is). They start off tamely with optical and quantum computing, and then move on into slightly more esoteric models like DNA computing, culminating with ooze computing and water wave computing (hey, I'm on a beach here, computing my legs off!). One of the more interesting proposals was something called 'reversible computing':

  Every computing operation involves feeding inputs into logic gates, which produce output signals. Instead of discarding the energy of those signals, Frank's gates run in reverse after every operation. That returns the energy of the output signal to the start of the circuit where it is used to carry a new input signal

  Of course, what's not clear to me is why this isn't a poor cousin of quantum computing, where as far as I understand all computations prior to a measurement are reversible.
  

But the idea of reversible computing gets back to very deep ideas about entropy and the second law of thermodynamics. Think of a box partitioned into two parts, each containing air at the same (global) temperature. In the partition is a small passage, guarded by a tiny demon, who only lets molecules go from left to right if they are hotter than average, and from right to left if they are colder than average. Over time, the right side of the container gets hotter and hotter, and the left side gets colder and colder. This demon is Maxwell's demon, posited to try and find a contradiction in the Second Law of Thermodynamics.

One of the more famous refutations of this apparent paradox was by Leo Szilard, who argued that in order for the demon to do its job, it must somehow gather information about the average temperature, and this gathering of information costs energy. Rolf Landauer famously showed in 1960 that reversible computations need not increase thermodynamic entropy (and also information entropy), and these facts were expanded by Charles Bennett to argue that eventually, a demon that does the desired job must run out of space and start deleting information, an irreversible (and therefore entropy increasing) operation. It's a streaming algorithm !!

There's a book that collects all this work together: Maxwell's Demon 2: Entropy, Classical and Quantum Information, Computing. It's been on my list of 'books to read' for a long time now.