Toluu : Shtetl-Optimized

Shtetl-Optimized

The Blog of Scott Aaronson

At least three people have now asked my opinion of the paper Mathematical Undecidability and Quantum Randomness by Paterek et al., which claims to link quantum mechanics with Gödelian incompleteness. Abstract follows:

We propose a new link between mathematical undecidability and quantum physics. We demonstrate that the states of elementary quantum systems are capable of encoding mathematical axioms and show that quantum measurements are capable of revealing whether a given proposition is decidable or not within the axiomatic system. Whenever a mathematical proposition is undecidable within the axioms encoded in the state, the measurement associated with the proposition gives random outcomes. Our results support the view that quantum randomness is irreducible and a manifestation of mathematical undecidability.

Needless to say, the paper has already been Slashdotted. I was hoping to avoid blogging about it, because I doubt I can do so without jeopardizing my quest for Obamalike equanimity and composure. But similar to what’s happened several times before, I see colleagues who I respect and admire enormously�

Wanted: Better Wikipedia coverage of theoretical computer scienceNovember 26

A year ago, a group of CS theorists—including Eli Ben-Sasson, Andrej Bogdanov, Anupam Gupta, Bobby Kleinberg, Rocco Servedio, and your humble blogger, and fired up by the evangelism of Sanjeev Arora, Christos Papadimitriou, and Avi Wigderson—agreed to form a committee to improve Wikipedia’s arguably-somewhat-sketchy coverage of theoretical computer science. One year later, our committee of busy academics has done, to a first approximation, nothing.

In considering this state of affairs, I’m reminded of the story of Wikipedia’s founding. Before Wikipedia there was Nupedia, where the articles had to be written by experts and peer-reviewed. After three years, Nupedia had produced a grand total of 24 articles. Then a tiny, experimental adjunct to Nupedia—a wiki-based peanut gallery where anyone could contribute—exploded into the flawed, chaotic, greatest encyclopedia in the history of the world that we all know today.

Personally, I’ve never understood academics (and there are many) who sneer at Wikipedia. I’ve been both an awestruck admirer of it and a massive waster of time on it since shortly after it came out. But I also accept the reality that Wikipedia is fundamentally an amateur achievement. It will never be an ideal venue for academics—not only because we don’t have the time, but because we’re used to (1) putting our names on our stuff, (2) editorializing pretty freely,

Sundry and VariousNovember 21

1. There’s now a popular article by Lisa Zyga at physorg.com, about my paper with John Watrous on quantum computing with closed timelike curves. On the whole, I think Zyga did an excellent job at getting the facts (such as they are) correct.

2. Challenged ballots in the Coleman vs. Franken race: you be the judge!

3. One of the unfortunate things about not updating your blog often, I find, is that people assume you’re still obsessed with the last thing you blogged about, weeks after you’ve all but forgotten about it. As it happens, I’ve now fully recovered from the joy of the election, and am back to my normal angst-ridden equilibrium. On the other hand, I’ve not yet recovered from the STOC deadline.

4. My quest to become more obamalike in temperament is now officially a failure. I should try it again sometime.

The unfamiliar burden of victoryNovember 4

On balance? I’ll take it.

Should you vote?November 4

(Assuming you’re eligible?)

An argument I came up with a while ago is that, in an election with N voters, the probability of your vote swaying the outcome could be expected to scale like 1/√N—but the utility to the world if your vote does sway the outcome could be expected to scale like N. Under those assumptions, the expected utility of your vote for the world scales like √N (or -√N, depending which candidate you vote for). So if you care about the world even ~1/√N as much as you care about yourself, you should probably vote, even though your vote almost certainly won’t change the outcome. Indeed, the case is even stronger in the US (at least if you live in a swing state), both because the electoral college amplifies the probability of your vote mattering (see the Majority-Is-Stablest Theorem), and because of the US’s disproportionate influence on the world.

A version of the above argument was discovered independently by Peter Norvig, who—appropriately for an applied rather than theoretical computer scientist—plugs in some actual numbers, rather than considering the asymptotics as the number of voters goes to infinity. Norvig finds an expected value of your vote to the United States of about $1 million (or $6 trillion divided by a 1 in 6 million chance of your vote mattering). Another version of th