Digressions loosely related to Scott Aaronson

“In fact, what really perplexes me is when I meet a smart, inquisitive person—let’s say a mathematician or scientist—who claims NOT to be obsessed with these huge issues! …. From my perspective, then, the best way to frame the question is not: “why be interested in philosophy?” Rather it’s: “why be interested in anything else?”

Scott Aaronson, theoretical computer scientist, in an interview on “Philosophical Progress”

(Warning: over 6,000 words)

I really like Scott Aaronson. The man knows his stuff (especially when it comes to theoretical computer science, in which he’s one of the big names), and he knows how to write. He can’t help but write engagingly, even when he’s writing for a more technical audience. (I linked to a post about large finite numbers, so if you’re a googologist too – even a wannabe like me who’s fumbled around with silly trial extensions of TREES and subcubics in his spare time – have a look!) I mean, he makes P vs. NP riveting.

That’s why this post, which two minutes ago was originally intended to be about a single short essay on quantum computing Scott wrote using only the ten hundred most used words in English, is now turning out to be a winding digression on interesting things Scott has written I’ve found in that two-minute period after that.

P vs. NP first. Sure, you can look up the Wikipedia article on the subject, or even its Simple English counterpart (which, knowing inferential distance and hindsight bias, isn’t actually as transparent as it makes itself out to be if your audience is “reasonably intelligent laypeople”), and there’s always the Clay Millennium Institute’s description of the problem (for those of you gunning for a million dollars – I’m kidding. I doubt you’d do it even mostly for the money – also, Perelman), and here’s a vastly comprehensive one-stop resource for all things P vs. NP that’d make sense if you’ve cleared the bar first, but the bar’s a high one, and few help you clear it better than Scott:

The short answer is: the biggest unsolved problem of theoretical computer science, and one of the deepest questions ever asked by human beings!  Here are four informal interpretations of the P vs. NP problem that people give, and which I can endorse as capturing the spirit of what’s being asked:

  • Are there situations where brute-force search—that is, trying an exponential number of possibilities one-by-one, until we find a solution that satisfies all the stated constraints—is essentially the best algorithm possible?
  • Is there a fast algorithm to solve the NP-complete problems—a huge class of combinatorial problems that includes scheduling airline flights, laying out microchips, optimally folding proteins, coloring maps, packing boxes as densely as possible, finding short proofs of theorems, and thousands of other things that people in fields ranging from AI to chemistry to economics to manufacturing would like to solve?  (While it’s not obvious a priori, it’s known that these problems are all “re-encodings” of each other.  So in particular, a fast algorithm for any one of the problems would imply fast algorithms for the rest; conversely, if any one of them is hard then then they all are.)
  • Is it harder to solve a math problem yourself than to check a solution by someone else? [[This is where you insert a comment about the delicious irony, that P vs. NP itself is a perfect example of a monstrously-hard problem for which we could nevertheless recognize a solution if we saw one—and hence, part of the explanation for why it’s so hard to prove P≠NP is that P≠NP…]]
  • In the 1930s, Gödel and Turing taught us that not only are certain mathematical statements undecidable(within the standard axiom systems for set theory and even arithmetic), but there’s not even an algorithm to tell which statements have a proof or disproof and which don’t.  Sure, you can try checking every possible proof, one by one—but if you haven’t yet found a proof, then there’s no general way to tell whether that’s because there is no proof, or whether you simply haven’t searched far enough.  On the other hand, if you restrict your attention to, say, proofs consisting of 1,000,000 symbols or less, then enumerating every proof does become possible.  However, it only becomes “possible” in an extremely Platonic sense: if there are 21,000,000 proofs to check, then the sun will have gone cold and the universe degenerated into black holes and radiation long before your computer’s made a dent.  So, the question arises of whether Gödel and Turing’s discoveries have a “finitary” analogue: are there classes of mathematical statements that haveshort proofs, but for which the proofs can’t be found in any reasonable amount of time?

Basically, P vs. NP is the mathematical problem that you’re inevitably led to if you try to formalize any of the four questions above.

Here’s Scott Alexander (of Slate Star Codex) writing on Scott Aaronson’s new book Quantum Computing Since Democritus. He’s entertaining as usual:

I think the biggest thing I got was – I had always thought of the physicists’ God as a basically benevolent guy who fine tunes constants to create a world capable of both astounding complexity and underlying simplicity.

The vision I got from Democritus was of a God who was single-mindedly obsessed with enforcing a couple of rules about certain types of information you are not allowed to haveunder any circumstances. Some of these rules I’d already known about. You can’t have information from outside your light cone. You can’t have information about the speed and position of a particle at the same time. Others I hadn’t thought about as much until readingDemocritus. Information about when a Turing machine will halt. Information about whether certain formal systems are consistent. Precise information about the quantum state of a particle. The reason God hasn’t solved world poverty yet is that He is pacing about feverishly worried that someone, somewhere, is going to be able to measure the quantum state of a particle too precisely, and dreaming up new and increasingly bizarre ways He can prevent that from happening.

Aaronson goes one level deeper than most of the other popular science writers I know and speculates on why the laws of physics are the way they are. Sometimes this is the elegance and complexity route – in his chapter on quantum physics, he argues that quantum probabilities are the squares of amplitudes because if the laws of physics were any other way – the fourth power of amplitudes, or whatever – it would fail to preserve certain useful mathematical properties. But in other cases, it’s back to Obsessive God – the laws of physics are carefully designed to preserve the rules about what information you are and aren’t allowed to have.

Aaronson tries to tie his own specialty, computational complexity theory, into all of this. It’s hard for me to judge how successful he is. The few times he tries to tie it into areas of philosophy I know something about – like free will – I’m not too impressed. But I could be misunderstanding him.

But once again, you get the feeling that computational complexity is about what information God will and won’t let you have. It’s a little less absolute – more “you can’t have this information without doing the full amount of work” rather than a simple no – but it seems like the same principle. There are a bunch of situations in the book where Aaronson takes something we don’t really know that much about and says it has to be a certain way, because if it were any other way, it could be used to solve NP problems in polynomial time, and there’s no way God’s going to let us do that.

He includes a couple of quotes from the book which, in conjunction with the glowing reviews over at Amazon.com, immediately made me feel like getting the book and getting it now:

You can look at Deep Blue, the Robbins conjecture, Google, most recently Watson – and say that’s not really AI. That’s just massive search, helped along by clever programming. Now this kind of talk drives AI researchers up a wall. They say: if you told someone in the 1960s that in 30 years we’d be able to beat the world grandmaster at chess, and asked if that would count as AI, they’d say of course it’s AI. But now that we know how to do it, it’s no longer AI – it’s just search.

(Typical moving-the-goalposts argument, which I just learned today is also called the gravity game)

The third thing that annoys me about the Chinese Room argument is the way it gets so much mileage from a possibly misleading choice of imagery, or, one might say, by trying to sidestep the entire issue of computational complexity purely through clever framing. We’re invited to imagine someone pushing around slips of paper with zero understanding or insight, much like the doofus freshmen who write (a + b)^2 = a^2 + b^2 on their math tests. But how many slips of paper are we talking about! How big would the rule book have to be, and how quickly would you have to consult it, to carry out an intelligent Chinese conversation in anything resembling real time? If each page of the rule book corresponded to one neuron of a native speaker’s brain, then probably we’d be talking about a “rule book” at leas the size of the Earth, its pages searchable by a swarm of robots traveling at close to the speed of light. When you put it that way, maybe it’s not so hard to imagine this enormous Chinese-speaking entity that we’ve brought into being might have something we’d be prepared to call understanding or insight.

I’d like to see Searle (who came up with Chinese Room) actually go head-on against this argument, instead of side-stepping it with stuff about “intentionality” and “simulation is not duplication” etc. Really, once you internalize the idea of “truth” as simply a linguistically convenient way of expressing map-territory correspondence a la Tarski’s “‘Snow is white’ iff snow is white”, it becomes hard to seriously entertain notions like “intentionality”. Also, Blindsight. But I digress. 

My contention in this chapter is that quantum mechanics is what you would inevitably come up with if you started from probability theory, and then said, let’s try to generalize it so that the numbers we used to call “probabilities” can be negative numbers. As such, the theory could have been invented by mathematicians in the nineteenth century without any input from experiment. It wasn’t, but it could have been. And yet, with all the structures mathematicians studied, none of them came up with quantum mechanics until experiment forced it on them.


Imagine there’s a very large population of people in the world, and that there’s a madman. What the madman does is, he kidnaps ten people and puts them in a room. He then throws a pair of dice. If the dice land snake-eyes (two ones) then he murders everyone in the room. If the dice do not land snake-eyes, then he releases everyone, then kidnaps 100 new people. He now does the same thing: he rolls two dice; if they land snake-eyes, he kills everyone, and if they don’t land snake-eyes, then he releases them and kidnaps 1000 people. He keeps doing this until he gets snake-eyes, at which point he’s done. So now, imagine that you’ve been kidnapped. Conditioned on that fact, how likely is it that you’re going to die? One answer is that the dice have a 1/36 chance of landing snake eyes, so you should only be a “little bit” worried (considering). A second reflection you could make is to consider, of people who enter the room, what the fraction is of people who ever get out. About 8/9 of the people who ever go into the room will die.

This is the Doomsday argument. This makes me go goshdangit WHY

There’s a joke about a planet full of people who believe in anti-induction: if the sun has risen every day in the past, then today, we should expect that it won’t. As a result, these people are all starving and living in poverty. Someone visits the planet and tells them, “Hey, why are you still using this anti-induction philosophy? You’re living in horrible poverty!” They answer, “Well, it never worked before.”

Ha. How to update? 

Quantum mechanics does offer a way out [the philosophical puzzle about whether you “survive” a teleportation where a machine scans you on an atomic level, radios the data to Mars, another machine on Mars makes an atom-for-atom copy of you, and then the original is destroyed]. Suppose some of the information that made you you was actually quantum information. Then, even if you were a thoroughgoing materialist, you could still have an excellent reason not to use the teleportation machine – because, as a consequence of the No-Cloning Theorem, no such machine could possibly work as claimed.

Finally, on the clearest explanation of the halting problem I’ve seen in a while:

Can we prove there’s no program to solve the halting problem? This is what Turing does. His key idea is not even to try to analyze the internal dynamics of such a program, supposing it existed. Instead he simply says, suppose by way of contradiction that such a program P exists. Then we can modify P to produce a new program P’ that does the following. Given another program Q as its input, P’:

1) Runs forever if Q halts given its own code as input, or
2) Halts if Q runs forever given its own code as input

Now we just feed P’ its own code as input. By the conditions above, P’ will run forever if it halts, or halt if it runs forever. Therefore, P’ – and by implication P – can’t have existed in the first place.

Of course you have nicer versions, e.g. this poem, but – I take that back. Re-reading the poem made me realize just how cool it was:

Scooping the Loop Snooper

No general procedure for bug checks will do.
Now, I won’t just assert that, I’ll prove it to you.
I will prove that although you might work till you drop,
you cannot tell if computation will stop.

For imagine we have a procedure called P
that for specified input permits you to see
whether specified source code, with all of its faults,
defines a routine that eventually halts.

You feed in your program, with suitable data,
and P gets to work, and a little while later
(in finite compute time) correctly infers
whether infinite looping behavior occurs.

If there will be no looping, then P prints out ‘Good.’
That means work on this input will halt, as it should.
But if it detects an unstoppable loop,
then P reports ‘Bad!’ — which means you’re in the soup.

Well, the truth is that P cannot possibly be,
because if you wrote it and gave it to me,
I could use it to set up a logical bind
that would shatter your reason and scramble your mind.

Here’s the trick that I’ll use — and it’s simple to do.
I’ll define a procedure, which I will call Q,
that will use P’s predictions of halting success
to stir up a terrible logical mess.

For a specified program, say A, one supplies,
the first step of this program called Q I devise
is to find out from P what’s the right thing to say
of the looping behavior of A run on A.

If P’s answer is ‘Bad!’, Q will suddenly stop.
But otherwise, Q will go back to the top,
and start off again, looping endlessly back,
till the universe dies and turns frozen and black.

And this program called Q wouldn’t stay on the shelf;
I would ask it to forecast its run on itself.
When it reads its own source code, just what will it do?
What’s the looping behavior of Q run on Q?

If P warns of infinite loops, Q will quit;
yet P is supposed to speak truly of it!
And if Q’s going to quit, then P should say ‘Good.’
Which makes Q start to loop! (P denied that it would.)

No matter how P might perform, Q will scoop it:
Q uses P’s output to make P look stupid.
Whatever P says, it cannot predict Q:
P is right when it’s wrong, and is false when it’s true!

I’ve created a paradox, neat as can be —
and simply by using your putative P.
When you posited P you stepped into a snare;
Your assumption has led you right into my lair.

So where can this argument possibly go?
I don’t have to tell you; I’m sure you must know.
A reductio: There cannot possibly be
a procedure that acts like the mythical P.

You can never find general mechanical means
for predicting the acts of computing machines;
it’s something that cannot be done. So we users
must find our own bugs. Our computers are losers!

Here are three short essays on quantum computing explained to a lay audience using only the ten hundred most commonly used words in English:


I study computers that would work in a different way than any computer that we have today.  These computers would be very small, and they would use facts about the world that are not well known to us from day to day life.  No one has built one of these computers yet—at least, we don’t think they have!—but we can still reason about what they could do for us if we did build them.

How would these new computers work? Well, when you go small enough, you find that, in order to figure out what the chance is that something will happen, you need to both add and take away a whole lot of numbers—one number for each possible way that the thing could happen, in fact. What’s interesting is, this means that the different ways a thing could happen can “kill each other out,” so that the thing never happens at all! I know it sounds weird, but the world of very small things has been known to work that way for almost a hundred years.

So, with the new kind of computer, the idea is to make the different ways each wrong answer could be reached kill each other out (with some of them “pointing” in one direction, some “pointing” in another direction), while the different ways that the right answer could be reached all point in more or less the same direction. If you can get that to happen, then when you finally look at the computer, you’ll find that there’s a very good chance that you’ll see the right answer. And if you don’t see the right answer, then you can just run the computer again until you do.

For some problems—like breaking a big number into its smallest parts (say, 43259 = 181 × 239)—we’ve learned that the new computers would be much, much faster than we think any of today’s computers could ever be. For other problems, however, the new computers don’t look like they’d be faster at all. So a big part of my work is trying to figure out for which problems the new computers would be faster, and for which problems they wouldn’t be.

You might wonder, why is it so hard to build these new computers? Why don’t we have them already? This part is a little hard to explain using the words I’m allowed, but let me try. It turns out that the new computers would very easily break. In fact, if the bits in such a computer were to “get out” in any way—that is, to work themselves into the air in the surrounding room, or whatever—then you could quickly lose everything about the new computer that makes it faster than today’s computers. For this reason, if you’re building the new kind of computer, you have to keep it very, very carefully away from anything that could cause it to lose its state—but then at the same time, you do have to touch the computer, to make it do the steps that will eventually give you the right answer. And no one knows how to do all of this yet. So far, people have only been able to use the new computers for very small checks, like breaking 15 into 3 × 5. But people are working very hard today on figuring out how to do bigger things with the new kind of computer.

In fact, building the new kind of computer is so hard, that some people even believe it won’t be possible! But my answer to them is simple. If it’s not possible, then that’s even more interesting to me than if it ispossible! And either way, the only way I know to find out the truth is to try it and see what happens.

Sometimes, people pretend that they already built one of these computers even though they didn’t. Or they say things about what the computers could do that aren’t true. I have to admit that, even though I don’t really enjoy it, I do spend a lot of my time these days writing about why those people are wrong.

Oh, one other thing. Not long from now, it might be possible to build computers that don’t do everythingthat the new computers could eventually do, but that at least do some of it. Like, maybe we could use nothing but light and mirrors to answer questions that, while not important in and of themselves, are still hard to answer using today’s computers. That would at least show that we can do something that’s hard for today’s computers, and it could be a step along the way to the new computers. Anyway, that’s what a lot of my own work has been about for the past four years or so.

Besides the new kind of computers, I’m also interested in understanding what today’s computers can and can’t do. The biggest open problem about today’s computers could be put this way: if a computer can check an answer to a problem in a short time, then can a computer also find an answer in a short time? Almost all of us think that the answer is no, but no one knows how to show it. Six years ago, another guy and I figured out one of the reasons why this question is so hard to answer: that is, why the ideas that we already know don’t work.

Anyway, I have to go to dinner now. I hope you enjoyed this little piece about the kind of stuff that I work on.


Many years ago people thought about what computers can do and what computers can check. They had two roads to go: The first was to believe that computers can do everything that computers can check. This could be a great! The second was to believe that computers can not do everything that computers can check. This is not so great but very interesting! But this is what most people believe and try to understand. It will be great to understand it! But even this is very hard.

A little later people thought about a new kind of computers that can do a lot of things that our real computers can not do. Again they had two roads to go: The first was to believe that these new kind of computers can be built. This could be great! The second was to believe that these new kind of computers can not be built. This would not be so great but again it would be interesting and it would be great to understand the reasons. This time many people took the wrong road and believed that the new kind of computers can be built. They took the wrong road but they gave us a good ride for our money. Maybe they took the wrong road because they believed some guy with beautiful thoughts. But this guy was joking or just wrong.

Anyway, the road people took was the wrong road and my work is to explain why. My work has three parts. The first part is to explain what was stupid in what people thought: People missed that a computer is different from a car! The second part is to draw a different picture. This is hard and takes a lot of time. The third part is to explain why not to believe in these new computers: One reason is that the new computers are able go back in time in such a way we never saw before.

All this is very exciting!


The work these people do is saying what are all the great things we could do if we had a great great “new kind of computer”. In real life such a computer is not made yet. No one is even close to making it. Many people pretend we are close to such a computer. But we are not. There are many real problems in making such a computer. Most good people who study them understand this and agree. Other people want money or other things. So they lie and pretend to the world that this “new kind of computer” is right around the corner.

I think what these people study is like a game. They try to see what’s the best they could do for us within this game. Games are fun. Knowing about our world is also important. But we have to decide how much time, money and attention we give these people. I think we are giving them too much right now. How much money would you give someone to make you sure that this “new kind of computer” can not be built? Maybe we will learn some interesting things along the way. But it might be easier to try to learn them in other ways.

We have to learn to trust those who are good and do not lie about what their “new kind of computer” can do yet. We must also spend more on trying to actually make this “new kind of computer” and spend less on imagining what sorts of nice things we could do if only we had this “new kind of computer”. Imagine if hundred years before the first car was actually built hundreds of ten hundreds of people were given lots of time and money to tell you what sorts of great and fun things you could do if only you had a car.

These people have brothers who actually try to make today’s computers do more things and faster by thinking of new ways to do these same things. I think these brothers do important things but they do not get so much attention. That is a little sad.

Getting too long already, so I’ll end with a few quick quotes. Here’s one in an interview on the relevance of philosophy (the reason I started writing this post actually), which reminded me of Luke Muehlhauser’s comprehensively-referenced Philosophy is a Diseased Discipline series of posts (unsurprisingly because Luke himself is the interviewer. And before you start thinking I’m “dismissive of philosophy across the board” just because it was provocatively titled as such, click on that link first please!):

I think the latter question [“why be interested in anything else other than philosophy?”] has an excellent answer. A crucial thing humans learned, starting around Galileo’s time, is that even if you’re interested in the biggest questions, usually the only way to make progress on them is to pick off smaller subquestions: ideally, subquestions that you can attack using math, empirical observation, or both. For again and again, you find that the subquestions aren’t nearly as small as they originally looked! Much like with zooming in to the Mandelbrot set, each subquestion has its own twists and tendrils that could occupy you for a lifetime, and each one gives you a new perspective on the big questions. And best of all, you can actually answer a few of the subquestions, and be the first person to do so: you can permanently move the needle of human knowledge, even if only by a minuscule amount. As I once put it, progress in math and science — think of natural selection, Godel’s and Turing’s theorems, relativity and quantum mechanics — has repeatedly altered the terms of philosophical discussion, as philosophical discussion itself has rarely altered them! (Of course, this is completely leaving aside math and science’s “fringe benefit” of enabling our technological civilization, which is not chickenfeed either.)

On this view, philosophy is simply too big and too important to be confined to philosophy departments! Of course, the word “philosophy” used to mean the entire range of fundamental inquiry, from epistemology and metaphysics to physics and biology (which were then called “natural philosophy”), rather than just close textual analysis, or writing papers with names like “A Kripkean Reading of Wittgenstein’s Reading of Frege’s Reading of Kant.” And it seems clear to me that there’s enormous scope today for “philosophy” in the former sense — and in particular, for people who love working on the subquestions, on pushing the frontiers of neuroscience or computer science or physics or whatever else, but who also like to return every once in a while to the “deep” philosophical mysteries that motivated them as children or teenagers. Admittedly, there have been many great scientists who didn’t care at all about philosophy, or who were explicitly anti-philosophy. But there were also scientists like Einstein, Schrodinger, Godel, Turing, or Bell, who not only read lots of philosophy but (I would say) used it as a sort of springboard into science — in their cases, a wildly successful one. My guess would be that science ultimately benefits from both the “pro-philosophical” and the “anti-philosophical” temperaments, and even from the friction between them.

On the fact that “usually the only way to make progress on [the big questions] is to pick off smaller subquestions: ideally, subquestions that you can attack using math, empirical observation, or both”, Scott has written at length about this in a highly fascinating paper titled “Why Philosophers Should Care About Computational Complexity” whose abstract alone made me feel like devoting the weekend to reading the entire paper – unfortunately I can’t copy-paste from PDF because I’m computer-illiterate like that, so I’ll leave you with Scott’s own four choice pickings from that paper; if you’re interested in the meatier versions check the paper out!

(1) One of the biggest, oldest questions in the philosophy of science could be paraphrased as: “why is Occam’s Razor justified? when we find simple descriptions of past events, why do we have any grounds whatsoever to expect those descriptions to predict future events?” This, I think, is the core of Hume’s “problem of induction.” Now, I think theoretical computer science has contributed large insights to this question — including Leslie Valiant’s Probably Approximately Correct (PAC) learning model, for which he recently won the Turing Award; the notion of Vapnik-Chernonenkis (VC) dimension; and the notion of the universal prior from algorithmic information theory. In essence, these ideas all give you various formal models where Occam’s Razor provably works — where you can give “simplicity” a precise definition, and then see exactly why simple hypotheses are more likely to predict the future than complicated ones. Of course, a skeptic about induction could still ask: OK, but why are the assumptions behind these formal models justified? But to me, this represents progress! The whole discussion can now start from a more sophisticated place than before.

(2) One of the first questions anyone asks on learning quantum mechanics is, “OK, but do all these branches of the wavefunction really exist? or are they just mathematical constructs used to calculate probabilities?” Roughly speaking, Many-Worlders would say they do exist, while Copenhagenists would say they don’t. Of course, part of what makes the question slippery is that it’s not even completely clear what we mean by words like “exist”! Now, I’d say that quantum computing theory has sharpened the question in many ways, and actually answered some of the sharpened versions — but interestingly, sometimes the answer goes one way and sometimes it goes the other! So for example, we have strong evidence that quantum computers can solve certain specific problems in polynomial time that would require exponential time to solve using a classical computer. Some Many-Worlders, most notably David Deutsch, have seized on the apparent exponential speedups for problems like factoring, as the ultimate proof that the various branches of the wavefunction must literally exist: “if they don’t exist,” they ask, “then where was this huge number factored? where did the exponential resources to solve the problem come from?” The trouble is, we’ve also learned that a quantum computer could NOT solve arbitrary search problems exponentially faster than a classical computer could solve them — something you’d probably predict a QC could do, if you thought of all the branches of the wavefunction as just parallel processors. If you want a quantum speedup, then your problem needs a particular structure, which (roughly speaking) lets you choreograph a pattern of constructive and destructive interference involving ALL the branches. You can’t just “fan out” and have one branch try each possible solution — twenty years of popular articles notwithstanding, that’s not how it works! We also know today that you can’t encode more than about n classical bits into n quantum bits (qubits), in such a way that you can reliably retrieve any one of the bits afterward. And we have all lots of other results that make quantum-mechanical amplitudes feel more like “just souped-up versions of classical probabilities,” and quantum superposition feel more like just a souped-up kind of potentiality. I love how the mathematician Boris Tsirelson summarized the situation: he said that “a quantum possibility is more real than a classical possibility, but less real than a classical reality.” It’s an ontological category that our pre-mathematical, pre-quantum intuitions just don’t have a good name for.

(3) Many interesting philosophical puzzles boil down to what it means to know something: and in particular, to the difference between knowing something “explicitly” and knowing it only “implicitly.” For example, I mentioned in my essay the example of the largest “known” prime number. According to the Great InternetMersenne Prime Search, that number is currently 2^57885161 – 1. The question is, why can’t I reply immediately that I know a bigger prime number: namely, “the first prime larger than 2^57885161 – 1″? I can even give you an algorithm to find my number, which provably halts: namely, starting from 2^57885161, try each number one by one until you hit a prime! Theoretical computer science has given us the tools to sharpen a huge number of questions of this sort, and sometimes answer them. Namely, we can say that to know a thing “explicitly” means, not merely to have ANY algorithm to generate the thing, but to have a provably polynomial-time algorithm. That gives us a very clear sense in which, for example, 2^57885161 – 1 is a “known” prime number while the next prime after it is not. And, in many cases where mathematicians vaguely asked for an “explicit construction” of something, we can sharpen the question to whether or not some associated problem has a polynomial-time algorithm. Then, sometimes, we can find such an algorithm or give evidence against its existence!

(4) One example that I didn’t discuss in the essay — but a wonderful one, and one where there’s actually been huge progress in the last few years — concerns the question of how we can ever know for sure that something is “random.” I.e., even if a string of bits passes every statistical test for randomness that we throw it at, how could we ever rule out that there’s some complicated regularity that we simply failed to find? In the 1960s, the theory of Kolmogorov complexity offered one possible answer to that question, but a rather abstract and inapplicable one: roughly speaking, it said we can consider a string “random enough for our universe” if it has no computable regularities, if there’s no program to output the string shorter than the string itself. More recently, a much more practical answer has come from the Bell inequality — and in particular, from the realization that the experimental violation of that inequality can be used to produce so-called “Einstein-certified random numbers.” These are numbers that are provably random, assuming only (a) that they were produced by two separated devices that produced such-and-such outputs in response to challenges, and (b) there was no faster-than-light communication between the devices. But it’s only within the last few years that computer scientists figured out how to implement this striking idea, in such a way that you get out more randomness than you put in. (Recently, two MIT grad students proved that, starting from a fixed “seed” of, let’s say, 100 random bits, you can produce unlimited additional random bits in this Einstein-certified way — see Infinite Randomness Expansion and Amplification with a Constant Number of Devices) And the experimental demonstration of these ideas is just getting started now. Anyway, I’m working on an article for American Scientist magazine about these developments, so rather than cannibalize the article, I’ll simply welcome people to read it when it’s done!


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s