« Criticizing global warming | Main | Your academic-journal dollars at work »
August 03, 2006
Things to read while the simulator runs; part 1
To commemorate the creation of a new recurrent topic here, two things caught my attention today:
Cosmic Variance, always an indelible source of cosmological weirdness, has a wonderfully detailed discussion about Boltzmann’s Anthropic Brain. That is, the argument that Boltzmann used, while thinking deeply about the nature of this entropy business and its incessant drumbeat of chaos, to explain the origin of the universe. The discussion begins with a simple questions "Why is the past different from the future, or equivalently, why was the entropy in the early universe so much smaller than it could have been?" and proceeds apace.
The unexpected consequence of Boltzmann’s microscopic definition of entropy is that the Second Law is not iron-clad — it only holds statistically... Faced with the deep puzzle of why the early universe had a low entropy, Boltzmann hit on the bright idea of taking advantage of the statistical nature of the Second Law. Instead of a box of gas, think of the whole universe. Imagine that it is in thermal equilibrium, the state in which the entropy is as large as possible. By construction the entropy can’t possibly increase, but it will tend to fluctuate, every so often diminishing just a bit and then returning to its maximum.
You can see where this is going: maybe our universe is in the midst of a fluctuation away from its typical state of equilibrium. The low entropy of the early universe, in other words, might just be a statistical accident, the kind of thing that happens every now and then. On the diagram, we are imagining that we live either at point A or point B, in the midst of the entropy evolving between a small value and its maximum. It’s worth emphasizing that A and B are utterly indistinguishable. People living in A would call the direction to the left on the diagram “the past,” since that’s the region of lower entropy; people living at B, meanwhile, would call the direction to the right “the past.”
Sean, our tour guide for this picturesque stroll through Boltzmann's mind, proceeds to explain why there is more going on here. Although the argument is flawed for more classical reasons, it also fails more directly because it doesn't account for things we can't hold Boltzmann responsible for not knowing: things like General Relativity, Inflation theory and Quantum Mechanics. It seems that the mystery of the arrow of time (or of time at all!) remains.
And finally, in case you have not been hiding under a rock for the past two years, you may have heard of a game called Sudoku. Many of my non-academic friends have succumbed to the faddishness of them, and I spy my neighbors on the plane scribbling away in books of these things. Even my younger sister is playing them now, on her Nintendo DS - oh, how the tools of procrastination have advanced since my youth, when we were forced to entertain ourselves with poorly wrapped bundles of dead trees. But, I do find Sudoku to be an interesting computational puzzle. That is, how difficult is it to solve these things, in general? The problem is clearly in NP, but not clearly NP-complete.
Lance Fortnow uses its NP membership as a nice little vehicle to explain how you can do a zero-knowledge interactive proof using Sudoku.
Victor has tried and failed to solve the latest Sudoku game and exclaims no solutions exists. His wife Paula has already solved the game. How does Paula convince Victor that a solution exists without giving the solution away?
It turns out that this can be easily done without the usual mapping to graph coloring. The result is intuitively pleasant and, because of Sudoku's popularity, probably highly accessible outside computer science. Not a bad use of something that reminds me of a glorified constraint optimization problem, or of that unpleasant "analytic" section of the GRE. In fact, any "puzzle" that can be solved by manually running a simple backtracking algorithm, or via first-order logic on the initial configuration, seems like a waste of brain power to me. Why not just write a computer program to solve it, and instead spend your time reading something interesting?
Update, Aug. 24: in truth, even problems that admit a more elegant solution can be solved by brute force via backtracking or reduction to satisfiability, but Sudoku doesn't yet admit such elegance, and I've never met anyone who solves them by doing something other than the two (boring) methods I mention. So, in my mind, by extension, that makes Sudoku a boring activity.
posted August 3, 2006 11:02 PM in Things to Read | permalink