Shtetl-Optimized

Another Update (Feb. 7): I have a new piece up at IEEE Spectrum, explaining why I made this bet.  Thanks to Rachel Courtland for soliciting the piece and for her suggestions improving it.

Update: My $100,000 offer for disproving scalable quantum computing has been Slashdotted.  Reading through the comments was amusing as always.  The top comment suggested that winning my prize was trivial: “Just point a gun at his head and ask him ‘Convinced?'”  (For the record: no, I wouldn’t be, even as I handed over my money.  And if you want to be a street thug, why limit yourself to victims who happen to have made public bets about quantum computing?)  Many people assumed I was a QC skeptic, and was offering the prize because I hoped to spur research aimed at disproving QC.  (Which is actually an interesting misreading: I wonder how much “pro-paranormal” research has been spurred by James Randi’s million-dollar prize?)  Other people said the bet was irrelevant since D-Wave has already built scalable QCs.  (Oh, how I wish I could put the D-Wave boosters and the QC deniers in the same room, and let them duke it out with each other while leaving me alone for a while!)  One person argued that it would be easy to prove the impossibility of scalable QCs, just like it would’ve been easy to prove the impossibility of scalable classical computers in 1946: the only problem is that both proofs would then be invalidated by advances in technology.  (I think he understands the word “proof” differently than I do.)  Then, buried deep in the comments, with a score of 2 out of 5, was one person who understood precisely:

I think he’s saying that while a general quantum computer might be a very long way off, the underlying theory that allows such a thing to exist is on very solid ground (which is why he’s putting up the money). Of course this prize might still cost him since if the news of the prize goes viral he’s going to spend the next decade getting spammed by kooks.

OK, two people:

There’s some needed context.  Aaronson himself works on quantum complexity theory.  Much of his work deals with quantum computers (at a conceptual level–what is and isn’t possible).  Yet there are some people who reject the idea the quantum computers can scale to “useful” sizes–including some very smart people like Leonid Levin (of Cook-Levin Theorem fame)–and some of them send him email, questions, comments on his blog, etc. saying so.  These people are essentially asserting that Aaronson’s career is rooted in things that can’t exist.  Thus, Aaronson essentially said “prove it.”  It’s true that proving such a statement would be very difficult … But the context is that Aaronson gets mail and questions all the time from people who simply assert that scalable QC is impossible, and he’s challenging them to be more formal about it.  He also mentions, in fairness, that if he does have to pay out, he’d consider it an honor, because it would be a great scientific advance.

For better or worse, I’m now offering a US$100,000 award for a demonstration, convincing to me, that scalable quantum computing is impossible in the physical world.  This award has no time limit other than my death, and is entirely at my discretion (though if you want to convince me, a good approach would be to convince most of the physics community first).  I might, also at my discretion, decide to split the award among several people or groups, or give a smaller award for a discovery that dramatically weakens the possibility of scalable QC while still leaving it open.  I don’t promise to read every claimed refutation of QC that’s emailed to me.  Indeed, you needn’t even bother to send me your refutation directly: just convince most of the physics community, and believe me, I’ll hear about it!  The prize amount will not be adjusted for inflation.

The impetus for this prize was a post on Dick Lipton’s blog, entitled “Perpetual Motion of the 21st Century?”  (See also this followup post.)  The post consists of a debate between well-known quantum-computing skeptic Gil Kalai and well-known quantum-computing researcher Aram Harrow (Shtetl-Optimized commenters both), about the assumptions behind the Quantum Fault-Tolerance Theorem.  So far, the debate covers well-trodden ground, but I understand that it will continue for a while longer.  Anyway, in the comments section of the post, I pointed out that a refutation of scalable QC would require, not merely poking this or that hole in the Fault-Tolerance Theorem, but the construction of a dramatically-new, classically-efficiently-simulable picture of physical reality: something I don’t expect but would welcome as the scientific thrill of my life.  Gil more-or-less dared me to put a large cash prize behind my words—as I’m now, apparently, known for doing!—and I accepted his dare.

To clarify: no, I don’t expect ever to have to pay the prize, but that’s not, by itself, a sufficient reason for offering it.  After all, I also don’t expect Newt to win the Republican primary, but I’m not ready to put $100,000 on the line for that belief.  The real reason to offer this prize is that, if I did have to pay, at least doing so would be an honor: for I’d then (presumably) simply be adding a little to the well-deserved Nobel Prize coffers of one of the greatest revolutionaries in the history of physics.

Over on Lipton’s blog, my offer was criticized for being “like offering $100,000 to anyone who can prove that Bigfoot doesn’t exist.”  To me, though, that completely misses the point.  As I wrote there, whether Bigfoot exists is a question about the contingent history of evolution on Earth.  By contrast, whether scalable quantum computing is possible is a question about the laws of physics.  It’s perfectly conceivable that future developments in physics would conflict with scalable quantum computing, in the same way that relativity conflicts with faster-than-light communication, and the Second Law of Thermodynamics conflicts with perpetuum mobiles.  It’s for such a development in physics that I’m offering this prize.

Update: If anyone wants to offer a counterpart prize for a demonstration that scalable quantum computing is possible, I’ll be happy for that—as I’m sure, will many experimental QC groups around the world.  I’m certainly not offering such a prize.

Follow

If you’re in academia and haven’t done so yet, please take a moment to sign this online petition organized by Tyler Neylon, and pledge that you won’t publish, referee, or do editorial work for any Elsevier journals.  I’ve been boycotting Elsevier (and most other commercial journal publishers—Elsevier is merely the worst) since 2004, when I first learned about their rapacious pricing policies.  I couldn’t possibly be happier with my choice: unlike most idealistic principles, this one gets you out of onerous work rather than committing you to it!  Sure, Elsevier is huge and we’re tiny, but the fight against them is finally gathering steam (possibly because of Elsevier’s support for the “Research Works Act”), years after the case against them became inarguable.  Since their entire business model depends on our donating free labor to them, all it will take to bring them down is for enough of us to decide we’re through being had.  We can actually win this one … Yes We Can.

For more information, see this wonderful recent post by Fields medalist and Shtetl-Optimized commenter Timothy Gowers, entitled “Elsevier — my part in its downfall.”  (Added: also check out this great post by Aram Harrow.)  You might also enjoy a parody piece I wrote years ago, trying to imagine how Elsevier’s “squeeze those dupes for all they’ve got” business model would work in any other industry.

Follow

A year ago, in a post entitled Anti-Complexitism, I tried to grapple with the strange phenomenon—one we’ve seen in force this past week—of anonymous commenters getting angry about the mere fact of announcements, on theoretical computer science blogs, of progress on longstanding open problems in theoretical computer science.  When I post something about global warming, Osama Bin Laden, or (of course) the  interpretation of quantum mechanics, I expect a groundswell of anger … but a lowering of the matrix-multiplication exponent ω?  Huh?  What was that about?

Well, in this case, some commenters were upset about attribution issues (which hopefully we can put behind us now, everyone agreeing about the importance of both Stothers’ and Vassilevska Williams’ contributions), while others honestly but mistakenly believed that a small improvement to ω isn’t a big deal (I tried to explain why they’re wrong here).  What interests me in this post is the commenters who went further, positing the existence of a powerful “clique” of complexity bloggers that’s doing something reprehensible by “hyping” progress in complexity theory, or by exceeding some quota (what, exactly?) on the use of the word “breakthrough.”

One of the sharpest responses to that paranoid worldview came (ironically) from a wonderful anonymous comment on my Anti-Complexitism post, which I recommend everyone read.  Here was my favorite paragraph:

The final criticism [by the anti-complexites] seems to be: complexity theory makes too much noise which people in other areas do not like.  I really don’t understand this one, I mean what is wrong with people in an area being excited about their area?  Is that wrong?  And where do we make those noise?  On complexity blogs!  If you don’t like complexity theorists being excited about their area why are you reading these blogs?  The metaphor would be an outsider going to a wedding and asking the people in the wedding with a very serious tone: “why is everyone happy here?”

Yesterday, in response to my reposting the above comment on Lance and Bill’s blog, another anonymous commenter had something extremely illuminating to say:

Scott, you are missing the larger socio-economical context: it’s not about excitement.  It’s about researchers competing for scarce resources, primarily funding.  The work involved in funding acquisition is generally loathed, and directly reduces the time scientists have for research and teaching.  If some researchers ramp up their hype-level vis-a-vis the rest of the community, as the complexity community is believed to be doing (what with all them Goedel awards?), they are forcing (or are seen as forcing) the rest either to accept a lower level of funding with all the concomitant disadvantages, or invest more time in hype themselves.  In other words, hypers are defecting in the prisoners dilemma type game scientists are playing, the objective of which is to minimise the labour involved in funding acquisition.

This is similar to teeth-whitening: in the past, it was perfectly possible to be considered attractive with natural, slightly yellowish teeth. Then some defected by bleaching, then more and more, and today natural teeth are socially hardly acceptable, certainly not if you want to be good-looking.  Is that progress?

I posted a response on Lance and Bill’s blog, but then decided it was important enough to repost here.  So:

Dear Anonymous 2:47,

Let me see whether I understand you correctly.  On the view you propose, other scientists shouldn’t have praised (say) Carl Sagan for getting millions of people around the world excited about science.  Rather, they should have despised him, for using hype to divert scarce funding dollars from their own fields to the fields Sagan favored (like astronomy, or Sagan’s preferred parts of astronomy).  Sagan forced all those other scientists to accept a terrible choice: either accept reduced funding, or else sink to Sagan’s level, and perform the loathed task of communicating their own excitement about their own fields to the public.

Actually, there were other scientists who drew essentially that conclusion.  As an example, Sagan was famously denied membership in the National Academy of Sciences, apparently because of a few vocal NAS members who were jealous and resentful of Sagan’s outreach activities.  The view we’re now being asked to accept is that those NAS members are the ones who emerge from the story the moral victors.

So let me thank you, Anonymous 2:47: it’s rare for anyone to explain the motivation behind angry TCS blog comments with that much candor.

Now that the real motivation has (apparently) crawled out from underneath its rock, I can examine it and refute it.  The central point is simply that science isn’t a Prisoner’s-Dilemma-type game.   What you describe as the “socially optimal equilibrium,” where no scientists need to be bothered to communicate their excitement about their fields, is not socially optimal at all—neither from the public’s standpoint nor from science’s.

At the crudest level, science funding is not a fixed-size pie.  For example, when Congress was debating the cancellation of the Superconducting Supercollider, a few physicists from other fields eagerly jumped on the anti-SSC bandwagon, hoping that the SSC money might then get diverted to their own fields.  Ultimately, of course, the SSC was cancelled, and none of the money ever found its way to other areas of physics.

So, if you see people using blogs to talk about research results that excite them, then instead of resenting it, consider starting your own blog to talk about the research results that excite YOU.  If your blog is well-written and interesting, I’ll even add you to my blogroll, game-theoretic funding considerations be damned.  Just go to WordPress.com—it’s free, and it takes only a few minutes to set one up.

Follow

Lance Fortnow now has a post up about how wonderful Graham Spanier and Joe Paterno were, and how sorry he is to see them go.

For what it’s worth, I take an extremely different view.  I’d be thrilled to see the insane football culture at many American universities—the culture that Spanier and Paterno epitomized—brought down entirely, and some good might yet come of the Penn State tragedy if it helps that happen.  Football should be, as it is at MIT, one of many fine extracurricular activities that are available to interested students (alongside table tennis, glassblowing, robot-building…), rather than a primary reason for a university’s existence.

What’s interesting about the current scandal is precisely that it establishes some finite upper bound on what people will tolerate, and thereby illustrates just what it takes for the public to turn on its football heroes.  Certainly the destruction of academic standards doesn’t suffice (are you kidding?).  More interestingly, sexism, sexual harassment, and “ordinary” rape—offenses that have brought down countless male leaders in other fields—barely even make a dent in public consciousness where football stars are concerned.  With child rape, by contrast, one can actually find a non-negligible fraction of Americans who consider it comparable in gravity to football.  (Though, as the thousands of rioting Penn State students reminded us, that’s far from a universal opinion.)  Many commentators have already made the obvious comparisons to the Catholic Church’s abuse scandal, and the lesson for powerful institutions the world over is indeed a similar one: sure, imprison Galileo; by all means stay silent during the Holocaust; but don’t protect pedophiles—cross that line, and your otherwise all-forgiving constituents might finally turn on you.

I should say that both of my parents are Penn State grads, and they’re both disgusted right now with the culture of hooliganism there—a culture that was present even in the late 60s and early 70s, but that’s become much more dominant since.  To the many of you at Penn State who want a university that’s more than an adjunct to a literally-rapacious football program, you have this blog’s admiration and support as you struggle to reclaim your great institution.  Go for the touchdown—WOOOOO!

Follow

A commenter named “Daniel Quilp” writes:

I am absolutely stunned that you have not posted an encomium to Steve Jobs.  You are a computer science professor.  Jobs was the most important innovator in the field.  You claim you want to reach out to the public but fail to take advantage of this opportunity.  Very sad, very disappointing.

Steve Jobs was indeed one of the great American innovators, and I was extremely sorry to hear about his passing.  I was riveted by the NYT obituary, from which I learned many facts about Jobs that I hadn’t known before.  Personally, I plan honor his memory by buying an iPhone 4S at the Apple Store near my apartment when it comes out on the 14th.  (I was debating between upgrading my 3GS to a 4S and switching to an Android, leaning toward 4S because of battery life.  The desire to honor the great man’s memory is what pushed me over the edge.)

As for why I didn’t write an encomium before: well, frankly, I don’t feel like being a theoretical computer scientist gives me any more of a “connection” to Steve Jobs than any of the hundreds of millions of people who use his products.  And when I do blog about world events, people often accuse me of jumping on a bandwagon and having nothing original to say, and tell me to stick to complexity theory.  That’s life as a blogger: not only is there nothing you can post, there’s nothing you can refrain from posting, that someone, somewhere, won’t be “absolutely stunned” by.

Even so, to anyone who was hurt or offended by my lack of a Steve Jobs post, I’m sorry.

And as long as I’m apologizing for silence about major news of the last week, I’m also sorry that I failed to congratulate the Royal Swedish Academy of Sciences for two truly magnificent decisions: first, awarding the Nobel Prize in Physics to Adam Riess, Saul Perlmutter, and Brian Schmidt for the discovery of the cosmic acceleration (see these two Cosmic Variance posts for more); second, awarding the Nobel Prize in Chemistry to Dan Shechtman for the discovery of quasicrystals.  If these two textbook-changing results don’t deserve Nobel Prizes, nothing does.

Since it’s Erev Yom Kippur, let me hereby repent for all of my countless mistakes, omissions, and lapses of judgment here at Shtetl-Optimized over the past year.  In the spirit of the “Kol Nidre” prayer, I also beg to be released from all survey articles that I promised to write, submissions that I promised to review, deadlines that I promised to meet, and emails that I promised to answer.  (Of course, if I were conventionally religious, I’d also have to repent for the very act of blogging on Yom Kippur.)

Follow

Update (8/16): Phew! By my count, I’ve answered 139 questions over the past few days. Thanks so much to everyone for submitting them, and please don’t submit any more!

Incidentally, to those of you who complain (correctly) that I no longer update this blog enough, there’s a simple solution that should carry you through at least the next year.  Namely, just read a few “Ask Me Anything” answers every week!  To help you with that, I’ve compiled the following abridged table of contents to my uninformed spoutings:

• Whether P=NP would let you violate the Second Law
• Whether mathematicians will (still) like complexity theory in the year 2100
• Transhumanism and its relation to quantum computing
• The hardness of simulating Newtonian physics
• How much I’d pay for a D-Wave One
• My views on mathematical definiteness, favorite areas of CS, and favorite philosophers
• How hard can problems in P get?
• The “higher education bubble,” and whether people should think twice before going to college
• Will the center of scientific gravity shift from the US to China?
• My “creative process” (such as it is), and whether I’d leave academia
• Israel, Libya, Egypt
• Worst-case versus best-case running time
• Favorite ice cream
• Favorite sci-fi writer
• The status of my “$25 Challenge”
• Wikipedia, and “nerd versus Jew”
• How Umesh Vazirani manages students
• Free jazz
• Neanderthal-level machine intelligence
• The value of oracles
• Decision problems versus function problems
• Software patents
• Quantum computing and complexity breakthroughs of the past decade
• Super-strong derandomization, and what I’d ask an alien
• Terry Tao
• How I justify attending conferences
• Scientific work in languages other than English
• Simple things in math and CS that I don’t understand
• Whether I’d rather solve P vs. NP or meet aliens
• Borders of a Palestinian state
• Why 20% of Americans can’t locate the US on a world map
• My greatest fears
• Open-access journals
• The existence of God
• MIT undergrads
• The history of complexity theory, and “why” IP=PSPACE should hold
• Favorite movie, favorite novel, favorite theorem
• Which charity I’d donate $1,000,000 to
• Favorite quantum information results of the last year
• My location on the political spectrum
• The 1-year anniversary of the Deolalikar Affair
• Teaching people the difference between rationalism and empiricism
• What happened to “Physics for Doofuses”?
• What happened to “Quantum Computing Since Democritus”?
• Proving P!=NP by exploiting structure of specific NP-complete problems
• Zionism, pacifism, Iraq, Vietnam, death penalty, abortion
• Drugs and alcohol
• Computer-assisted theorem proving
• Why to care about P vs. NP, and whether computers will solve it first
• Obama
• Whether I ever worked on P vs. NP
• Yellow books
• Interpreting barriers to proving P!=NP as logical independence statements
• The nature of time
• She believes in ghosts, he’s a scientific rationalist
• Research projects for undergrads
• Classification of polynomial-time algorithms
• Is the universe finite or infinite?
• Quantum algorithms beyond Shor/Grover/quantum simulation
• Will theoretical computer science “converge” with psychology?
• Are sexual preferences “socially constructed”?
• Should religions be judged by their scriptures?
• What to do if you think you can multiply matrices in near-linear time
• MathCamp
• Would I want P to equal NP?
• My late cat
• Bosons versus photons
• The relativization operator and Leibniz’s Law
• Do I feel guilty about my advantages, as I “dine in exclusive Boston eateries”?
• The Aaron Swartz case

Update: Thanks for the many, many, many great questions!  To keep things slightly under control, I’ll be fielding questions that are asked before 9PM EST tonight.

Also, sorry my blog went down for an hour!  I always count on Bluehost to not be there when I need it.

Alright, I put it off for most of the summer, but I guess it’s as good a time as any, now that (a) I’m finally done philosophizing for a while and (b) my wife Dana is away at a workshop, her civilizing and nerdiness-moderating influences temporarily absent.

So, by popular demand, and as promised a couple months ago, for the next 24 hours (with intermittent sleep breaks), I’ll once again be fielding any and all questions in the comments section.  Four simple ground rules:

1. No multi-part questions: one question per comment and three total per person.
2. While you can ask anything, if it’s too hostile, nosy, or irritating I might not answer it…
3. I’ll only answer the first three questions about academic career advice (since in previous Ask Me Anything posts, that topic tended to drown out everything else).
4. No questions that require me to read an article, watch a video, etc.

Follow

We live in perilous times.  Within a few days, the United States might default on its debt, plunging the country into an unprecedented catastrophe.  Meanwhile, the tragedy in Norway (a country I’ll visit for the first time next month) reminds us that the civilized world faces threats from extremists of every ideology.  All this news, of course, occurs against the backdrop of record-breaking heatwaves, the decimation of worldwide fish stocks, the dwindling supply of accessible oil, and the failure of the Large Hadron Collider to find supersymmetry.

But although the future may have seldom seemed bleaker, I want people to know that we in MIT’s complexity theory group are doing everything we can to respond to the most pressing global challenges.  And nothing illustrates that commitment better than a beautiful recent paper by my PhD student Andy Drucker (who many of you will recognize from his years of insightful contributions to Shtetl-Optimized: most recently, solving an open problem raised by my previous post).

Briefly, what Andy has done is to invent—and demonstrate—a breakthrough method by which anyone, including you, can easily learn to multiply ten-digit numbers in your head, using only a collection of stock photos from Flickr to jog your memory.

Now, you might object: “but isn’t it cheating to use a collection of photos to help you do mental math—just like it would be cheating to use pencil and paper?”  However, the crucial point is that you’re not allowed to modify or rearrange the photos, or otherwise use them to record any information about the computation while you’re performing it.  You can only use the photos as aids to your own memory.

By using his method, Andy—who has no special mental-math training or experience whatsoever—was able to calculate 9883603368 x 4288997768 = 42390752785149282624 in his head in a mere seven hours.  I haven’t tried the method myself yet, but hope to do so on my next long plane flight.

Crucially, the “Flickr method” isn’t limited to multiplication.  It works for any mental memorization or calculation task—in other words, for simulating an arbitrary Boolean circuit or Turing machine.  As I see it, this method provides probably the most convincing demonstration so far that the human brain, unaided by pencil and paper, can indeed solve arbitrary problems in the class P (albeit thousands of times more slowly than a pocket calculator).  In his paper, Andy discusses possible applications of the method for cognitive science: most notably, using it to test conjectures about the working of human memory.  If that or other applications pan out, then—like many other research projects that seem explicitly designed to be as useless as possible—Andy’s might end up failing at that goal.

Follow

(Thanks to Amit Sahai for spurring me to write this post!)

The Background

We all remember Gödel’s First Incompleteness Theorem from kindergarten.  This is the thing that, given a formal system F, constructs a sentence G(F) that’s a mathematical encoding of

“This sentence is not provable in F.”

If F proves G(F), then F proves both that F proves G(F) and that F doesn’t prove G(F), so F is inconsistent (and hence also unsound).  Meanwhile, if F proves Not(G(F)), then it “believes” there’s a proof of G(F).  So either that proof exists (in which case it would render F inconsistent, by the previous argument), or else it doesn’t exist (in which case F is unsound).  The conclusion is that, assuming F is powerful enough to express sentences like G(F) in the first place, it can’t be both sound and complete (that is, it can’t prove all and only the true arithmetical statements).

OK, but the way most people like to state Gödel’s Theorem is stronger than that: no sufficiently-powerful formal system F can be both complete and consistent.  Note that soundness implies consistency, but not vice versa.  (If I believe that there’s a giant purple boogeyman on the moon, then presumably my belief is unsound, but it might be perfectly consistent with my various other beliefs about boogeymen.)

Unfortunately, neither Gödel’s original proof, nor computer scientists’ favorite alternative proofs, actually give you the stronger statement about completeness and consistency.  And this has been a persistent problem when I teach Gödel in my undergraduate computability and complexity class.

Where’s the catch in Gödel’s argument?  It’s in the case where F proves Not(G(F)) (i.e., that G(F) is provable), even though in reality G(F) is true (i.e., G(F) isn’t provable).  In that situation, F would clearly be unsound, but it might not contain any contradiction—basically because, no matter how long you looked, you could never rule out F’s (false) belief that G(F) is provable.  Indeed, F would be what I like to call a self-hating theory: a theory, like F+Not(Con(F)), that pessimistically believes in its own inconsistency, even though in fact it’s perfectly consistent.  (By contrast, if F arrogantly believes in its own consistency, then it can’t be consistent by the Second Incompleteness Theorem!  There’s a lesson there somewhere…)

The way Gödel himself solved this problem was by introducing a new concept called ω-consistency, which is intermediate between consistency and soundness.  He then showed that F can’t be both complete and ω-consistent.  (Why didn’t Gödel simply talk about soundness?  Because unlike consistency or ω-consistency, soundness is a “metatheoretic” concept that’s impossible to formalize in F.  So, if he used soundness, then the First Incompleteness Theorem couldn’t even be stated, let alone proved, in F itself, and that in turn would create problems for the proof of his Second Incompleteness Theorem.)

Anyway, from the standpoint of an undergrad class, the fear is that, once you start talking about “ω-consistency,” all the romance and self-referential magic of Gödel will vanish in a morass of technicality.

So surely we can dot the i’s here (or rather, put the umlauts on the ö’s), and prove the stronger, cleaner statement that F can’t be both complete and consistent?

Yes we can—but to do so we need Rosser’s Theorem: a strengthening of Gödel’s Theorem from 1936 that’s much less well-known among the nerd public than it ought to be.  In Rosser’s proof, we replace G(F) by a new sentence R(F), which is a mathematical encoding of the following:

“For every proof of this sentence in F, there’s a shorter disproof.”

If F proves R(F), then it also proves that there’s a disproof of R(F) that’s shorter than the proof of R(F) whose existence we just assumed.  So we can look for that disproof (since there are only finitely many strings of symbols to check), and either we’ll find it or we won’t—but in either case, we’ll have revealed F to be inconsistent.  Meanwhile, if F proves Not(R(F)), then it proves that there is a proof of R(F) with no shorter disproof.  So in particular, it proves that there’s a proof of R(F) that’s no longer than the proof of Not(R(F)) whose existence we just assumed.  But once again, we can look for that proof (there are only finitely many strings to check), and either we’ll find it or we won’t, and in either case, F is revealed to be inconsistent.

Notice what the Rosser sentence accomplishes: it creates a symmetry between the cases that R(F) is provable and R(F) is disprovable, correcting the asymmetry between the two cases in Gödel’s original argument.

Alright, so then why don’t I just teach Rosser’s Theorem in my undergrad class, instead of Gödel’s?

I’ll tell you why: because, when I teach Gödel to computer scientists, I like to sidestep the nasty details of how you formalize the concept of “provability in F.”  (From a modern computer-science perspective, Gödel numbering is a barf-inducingly ugly hack!)

Instead, I simply observe Gödel’s Theorem as a trivial corollary of what I see as its conceptually-prior (even though historically-later) cousin: Turing’s Theorem on the unsolvability of the halting problem.

For those of you who’ve never seen the connection between these two triumphs of human thought: suppose we had a sound and complete (and recursively-axiomatizable, yadda yadda yadda) formal system F, which was powerful enough to reason about Turing machines.  Then I claim that, using such an F, we could easily solve the halting problem.  For suppose we’re given a Turing machine M, and we want to know whether it halts on a blank tape.  Then we’d simply have to enumerate all possible proofs in F, until we found either a proof that M halts, or a proof that M runs forever.  Because F is complete, we’d eventually find one or the other, and because F is sound, the proof’s conclusion would be true.  So we’d decide whether M halts.  But since we already know (thanks to Mr. T) that the halting problem is undecidable, we conclude that F can’t have existed.

“Look ma, no Gödel numbers!”

The “New” Observation

The above discussion leads to an obvious question:

Is there also a proof of Rosser’s Theorem that uses only Turing machines—analogous to the computer-scientist-friendly proof we just gave for the “original” Incompleteness Theorem?

My initial worry was that the answer would be no.  For not only is Rosser’s sentence more complicated than Gödel’s, but it depends essentially on an ordering of proofs—and it’s not clear what such an ordering would correspond to in the world of Turing machines.

Why did this worry me?  Because it threatened my conviction that computer programs are “really” at the core of Gödel’s Theorem, whatever any tradition-minded philosopher or logician might claim to the contrary.  If even the modest step from Gödel to Rosser required abandoning the computability perspective, then my faith in the Almighty Turing Machine would be shaken.

But never fear!  A few months ago, I found a short, simple, Turing-machine-based proof of Rosser’s Theorem.  While this seemed too small to write up as a paper, I’d never seen it before (please let me know if you have!), so I thought I’d share it here.  (Update: Makoto Kanazawa points me to a basically-similar argument in Kleene’s 1967 textbook.  So, you can consider what follows to be a “popularization” of Kleene.)

The first step is to define the following variant of the halting problem:

The Consistent Guessing Problem

Given as input a description of a Turing machine M:

1. If M accepts on a blank tape, then accept.
2. If M rejects on a blank tape, then reject.
3. If M runs forever on a blank tape, then either accept or reject, but in any case, halt!

It’s easy to show that there’s no Turing machine to solve the Consistent Guessing Problem, by a modification (arguably, even a simplification) of Turing’s original argument for the halting problem.  Indeed, I put the unsolvability of the Consistent Guessing Problem on last semester’s midterm, and at least half the students got it.  (Damn!  I guess I can’t use that one again.)

See it yet?  No?  Alright, so let P be a Turing machine that solves the Consistent Guessing Problem.  Then we can easily modify P to produce an new Turing machine Q that, given as input a description ⟨M⟩ of another Turing machine M:

• Rejects if M(⟨M⟩) accepts.
• Accepts if M(⟨M⟩) rejects.
• Halts (either accepting or rejecting) if M(⟨M⟩) runs forever.

Now run Q on its own description ⟨Q⟩.  If Q(⟨Q⟩) accepts, then it rejects; if Q(⟨Q⟩) rejects, then it accepts.  So the only remaining option is that Q(⟨Q⟩) runs forever, violating the third condition.

From the unsolvability of the Consistent Guessing Problem, I claim that Rosser’s Theorem follows.  For suppose we had a complete and consistent (but not necessarily sound!) formal system F, which was powerful enough to talk about Turing machines.  Then using F, we could solve the Consistent Guessing Problem, as follows.  Given as input a Turing machine description ⟨M⟩, start enumerating all possible proofs and disproofs of the statement “M accepts on a blank tape.”  Accept as soon as you find a proof, or reject as soon as you find a disproof.

Because F is complete, you must eventually find either a proof or a disproof (and therefore halt, either accepting or rejecting).  Also, because F is consistent, if M really rejects then F can’t prove that M accepts, while if M really accepts then F can’t prove that M doesn’t accept (since in either case, the contradiction could be discovered in finite time).  So you’ll accept if M accepts and reject if M rejects.  But this means that you’re solving Consistent Guessing!  Since we already showed there’s no Turing machine to solve Consistent Guessing, we conclude that F can’t have existed.

QED: the moral order of the universe is restored, and the Turing machine’s exalted position at the base of all human thought reaffirmed.

(Incidentally, you might wonder whether Gödel’s Second Incompleteness Theorem, on the impossibility of a consistent F proving its own consistency, can also be proved in a Turing-machine-centric way.  To anticipate your question, the answer is yes—and better yet, it even involves Kolmogorov complexity!  See, for example, this beautiful recent paper by Shira Kritchman and Ran Raz.)

So, will Gödel’s Theorem always and forevermore be taught as a centerpiece of computability theory, and will the Gödel numbers get their much-deserved retirement?  I don’t see a reason why that shouldn’t happen—but alas, the consistency of my prediction isn’t enough to imply its metatheoretic truth.

Follow

We’ve all been there before: by the time you start graduate school in Princeton, you’ve already invented the Turing machine, pioneered the concept of computational universality, and proved the unsolvability of Hilbert’s Entscheidungsproblem.  A few years from now, you’re going to return to England to make decisive contributions to the breaking of the Enigma and the winning of World War II.  Your problem is, what do you do for the couple years in between?  (Keep in mind that you have a PhD thesis to submit, and the Turing machine is already old hat by now!)

The answer, apparently, is to tackle a neat problem in logic, one version of which was asked three weeks ago by a Shtetl-Optimized commenter named Schulz.  Not knowing the answer, I posted Schulz’s problem to MathOverflow.  There, François Dorais and Philip Welch quickly informed me that Turing had already studied the problem in 1939, and Timothy Chow pointed me to Torkel Franzen’s book Inexhaustability: A Non-Exhaustive Treatment, which explains Turing’s basic observation and the background leading up to it in a crystal-clear way.

The problem is this: given any formal system F that we might want to take as a foundation for mathematics (for example, Peano Arithmetic or Zermelo-Fraenkel set theory), Gödel tells us that there are Turing machines that run forever, but that can’t be proved to run forever in F.  An example is a Turing machine M that enumerates all the proofs in F one by one, and that halts if it ever encounters a proof of 0=1.  The claim that M doesn’t halt is equivalent to the claim that F is consistent—but if F is indeed consistent, then the Second Incompleteness Theorem says that it can’t prove its own consistency.

On the other hand, if we just add the reasonable axiom Con(F) (which asserts that F is consistent), then our new theory, F+Con(F), can prove that M runs forever.  Of course, we can then construct a new Turing machine M’, which runs forever if and only if F+Con(F) is consistent.  Then by the same argument, F+Con(F) won’t be able to prove that M’ runs forever: to prove that, we’ll need a yet stronger theory, F+Con(F)+Con(F+Con(F)).  This leads inevitably to considering an infinite tower of theories F₀, F₁, F₂, …, where each theory asserts the consistency of the ones before it:

F₀ = F

F_i = F_i-1 + Con(F_i-1) for all i≥1

But there’s no reason not to go further, and define another theory that asserts the consistency of every theory in the above list, and then another theory that asserts the consistency of that theory, and so on.  We can formalize this using ordinals:

F_ω = F + Con(F₀) + Con(F₁) + Con(F₂) + …

F_ω+i = F_ω+i-1 + Con(F_ω+i-1) for all i≥1

F_2ω = F_ω + Con(F_ω) + Con(F_ω+1) + Con(F_ω+2) + …

and so on, for every ordinal α that we can define in the language of F.  For every such ordinal α, we can easily construct a Turing machine M_α that runs forever, but that can’t be proved to run forever in F_α (only in the later theories).  The interesting question is, what happens if we reverse the quantifiers? In other words:

Given a Turing machine M that runs forever, is there always an ordinal α such that F_α proves that M runs forever?

This is the question Turing studied, but I should warn you that his answer is disappointing.  It turns out that the theories F_α are not as well-defined as they look.  The trouble is that, even to define a theory with infinitely many axioms (like F_ω or F_2ω), you need to encode the axioms in some systematic way: for example, by giving a Turing machine that spits out the axioms one by one.  But Turing observes that the power of F_α can depend strongly on which Turing machine you use to spit out its axioms!  Indeed, he proves the following theorem:

Given any Turing machine M that runs forever, there is some “version” of F_ω+1 (i.e., some way of encoding its axioms) such that F_ω+1 proves that M runs forever.

The proof is simple.  Assume for simplicity that F itself has only finitely many axioms (removing that assumption is straightforward).  Then consider the following Turing machine P for outputting the axioms of F_ω, which gives rise to a “version” of F_ω that we’ll call F_P:

Output the axioms of F

For t=0,1,2,…

If M halts in t steps or fewer, then output “Con(F_P)”; otherwise output “Con(F_t)”

Next t

You might notice that our description of P involves the very theory F_P that we’re defining!  What lets us get away with this circularity is the Recursion Theorem, which says (informally) that when writing a program, we can always assume that the program has access to its own code.

Notice that, if P ever output the axiom “Con(F_P)”, then F_P would assert its own consistency, and would therefore be inconsistent, by the Second Incompleteness Theorem.  But by construction, P outputs “Con(F_P)” if and only if M halts.  Therefore, if we assume F_P‘s consistency as an axiom, then we can easily deduce that M doesn’t halt.  It follows that the theory F_ω+1 := F_P + Con(F_P) proves that M runs forever.

One question that the above argument leaves open is whether there’s a Turing machine M that runs forever, as well as a system S of ordinal notations “extending as far as possible”, such that if we use S to define the theories F_α, then none of the F_α‘s prove that M runs forever.  If so, then there would be a clear sense in which iterated consistency axioms, by themselves, do not suffice to solve the halting problem.  Alas, I fear the answer might depend on exactly how we interpret the phrase “extending as far as possible” … elucidation welcome!

Update (June 29, 2011): In a comment, François Dorais comes to the rescue once again:

In connection with your last paragraph, Feferman has shown that there are paths through O such that the resulting theory proves all true ∏⁰₁ statements. [JSL 27 (1962), 259-316] Immediately after Feferman and Spector showed that not all paths through O do this. [JSL 27 (1962), 383-390] In particular, they show that any good path must be more complicated than O itself: the path cannot be ∏¹₁. In other words, there is no simple way to form a wellordered iterated consistency extension that captures all true ∏⁰₁ statements.

Follow

Here’s an interview with me by math grad student Samuel Hansen, as part of a podcast he runs called Strongly Connected Components.  (Also check out the interviews with Steven Rudich, Steven Rudich a second time, Lance Fortnow, Doron Zeilberger, and your other favorite stars of the nerdosphere!)  In the interview, I talk about my passion for baseball stats, what you don’t know about llama-breeding, the use of color in Matisse’s later works … oh all right, it’s mostly about quantum computing and P vs. NP.

Here’s a story I told for an event called Story Collider, which was back-to-back with a superb production of Breaking the Code (Hugh Whitemore’s acclaimed play about the life of Alan Turing) in Cambridge’s Central Square Theater.  I was honored to serve as a “scientific consultant” to the Breaking the Code production, and to do audience Q&A before and after a couple performances.  In the Story Collider, I talk about the “Turing phase” I went through as a teenager and Alan T.’s impact on my life.

(Note: For the past couple years, I’ve avoided talking much about my personal life on this blog, since I pride myself on being someone who learns from experience and adjusts his behavior accordingly.  But two months ago, something truly happy occurred in my life, and if you listen to the end of the Story Collider, you’ll find out what it was…)

One last personal note: I’m at the Federated Computing Research Conference in San Jose all week.  If you read Shtetl-Optimized, are here at FCRC, see me, and wouldn’t do so otherwise, come and say hi!

Follow