Forget it. Nothing is going to make the general public excited about theoretical computer science. The general public wouldn't be excited about theoretical computer science even if they did understand it.

For the general public, the question of theoretical computer science is as interesting as the question of how plumbing works. My computer, they would say, is like my toilet -- it does what it's supposed to do most of the time, and when it breaks down I pay money to get some random jerk in to fix it. I suppose there's some quite interesting details involved in how rainwater that falls into the mountains manages to find its way through a complicated series of pipes to come into my toilet whenever I press this button, but there are far more interesting things to think about, so let's leave those details to the experts.

If a prophet of plumbing did show up to explain all the presumably-fascinating-to-someone details of how the city's water supply works then it would probably hold my interest for the duration of a half-hour documentary, but then I'd get on with my life with only a marginally-increased respect for the plumbers who make it happen.

I'm sure that waiting for messiahs to show up is a pretty normal sort of human activity, but I'd hate to encourage it.

For the general public, the question of what makes up matter is as interesting as the question of how beer is made. Matter, they say, is just like beer -- sometimes it tastes different, but it's just there to quench my thirst and mellow me out. I suppose there are interesting details involved in making beer, but let's leave those to the experts.

When a prophet of beer (beer snob) does show up, I listen to a lot of descriptive words that don't mean much to me, learn some fascinating history, but then the next evening I'll still be ordering the same regular as I did last night.

And yet, against all that, Feynman and Hawking have sparked many peoples' interest in physics, even among those who will never run an experiment, or take a formal course. Computer science is not about computers, and there's no need to conflate it with using a computer. See http://csunplugged.com for some attempts to make CS interesting while teaching it to primary- and secondary- school aged children without using actual computers, for example.

Jeannette Wing (CMU's head of CS) started a project sponsored by Microsoft called "Computational Thinking" where she tried to make CS a mainstream tool to make decisions in life. She's probably still working on it, but I always found the idea too vague to have any impact. I remember that Daniel Sleator thought the same when she first talked about it (I was there). http://www.cs.cmu.edu/~CompThink/

Unfortunately, I do [believe you]. Nonetheless, if Hawking, Feynman, Sagan (and I'm surprised we've forgotten Einstein until now) are the 'prophets' to be held up for physics, they are the examples I would start from to look for a CS prophet. Hofstadter or Turing, as have been mentioned elsewhere, would get my vote. The one is dead, though, and the other has an excellent book or two, but not at all the public image or body of "bite-sized" work that those prophets of physics have.

It's a lot easier to get someone interested in something that they can look up at in the sky than something which is totally abstract.

This is part of the reason I switched from studying semiconductor physics to giant planets. Much prettier pictures on my slides, nowadays.

I mean it. You write hermetic formulas, and the thing does stuff for you. It can even do things you can't (like beat Kasparov at Chess). This is as close as the infinite wish-spell as you can get (besides strong AI, if we ever get it).

Sure my analogy points mainly to programming, but theoretical computer science can help you improve that, making you even more powerful. Now if that doesn't interest the general public, I don't know what will.

You don't think it's interesting that it's provably impossible to predict in general what will happen if you follow a set of instructions, even if you have the entire set of instructions sitting in front of you (Rice's theorem)? This is the only plausible path I've ever heard towards recovering a notion of free will in a deterministic universe: even if you know the entire state of the universe and the rules by which it operates, it's still mathematically impossible to predict the future in any way more efficient than just sitting back and letting it unfold.

And you don't think it's important that we can prove that finding Nash equilibria in large games is computationally difficult, and that the amount of computation required grows much faster than the number of the players in the game (http://www.cs.berkeley.edu/~christos/papers/cacmDGP-2.pdf)? You think the fact that it's literally impossible for large markets to compute optimal solutions doesn't have profound economic and political implications?

If all this stuff is really as uninteresting to you as the details of your plumbing, then good for you, I guess. Maybe this is just the wrong site for this sort of stuff; maybe the audience here is self-selected to be all the people who thought their CS theory classes were so boring that they dropped out and founded startups instead. But I'm in the same camp as Scott Aaronson: I think there are a lot of people out there who would be just as fascinated by the profound questions, results, and paradoxes of CS as they are by quantum mechanics and relativity, if these ideas were given the same level of exposure. Theoretical physics is both a much older and much larger field than theoretical CS, so it's not surprising that it's managed to come up with many more charismatic and insightful popularizers. That doesn't mean that CS is any less interesting or exciting.

I was merely speaking in the voice of "member of the general public" up there who probably can't be persuaded to find all this stuff as interesting as whiz-bang relativity/quantum mechanics/cosmology. Note that it's only the most whiz-bang bits of physics which capture the imagination of the general public too -- try explaining solid state physics or optics to the general public and watch their eyes glaze over.

I think that it's exciting, but it's not generally exiting.

> That if someone at FedEx could came up with an efficient way of finding the shortest paths for their trucks to follow, they would in the process have broken all modern cryptography

Slow down there there cowboy. Polynomial time is not enough. You need a reasonable constant factor and a small-enough degree.

To put it another way, N2 is too slow at Google-scale. (Actually, N lg N is too slow for some of their problems.)

What are the sci-fi things in CS? Really fast factoring and fast routing for a vacuum cleaner sales guy.

The one potential element is AI. But CS has largely abandoned what the public views as AI. And even when there's a public show of AI, think Watson, many in CS come and say, "that's not really AI". IMO, AI is where the public can catch on to CS. But AI isn't what's generally referred to as theoretical CS -- you won't see AI papers at FOCS/STOC.

[1] http://www.gnu.org/philosophy/right-to-read.html

« Repent, repent, miserable sinners ! Soon, I tell you, those machines you count on will turn against you ! Soon, yes, in 27 years ! »

I was surprised to find this old article from Time magazine back in 1956. It concerns the solution to Post's Problem, which the article describes quite succinctly as:

| The problem: Does each non-recursive, recursively enumerable set have the property that every recursively enumerable set is recursive in it? Post himself thought not, but it was not until young Friedberg came along that anyone had the proof.

Can you imagine a mass-market magazine publishing such a thing today? Perhaps it's unnecessary, since anyone interested in computability theory probably pays attention to blogs like Scott Aaronson's.

There's a quote from from Gödel later in the article that may also speak to the problem of popularization:

| "Unfortunately," says Czech-born Kurt Godel of the institute, "he wants to study medicine. An achievement like this at his age comes only once in a lifetime.

1. At that time (roughly 1859), the percentage of the population that was considered educated is much smaller than it is now, and many of those in the educated class where indepently wealthy (or directly sponsored by someone who was) and had little expectation on them other than to be educated.

2. Knowledge was much was less specialized then than it is now. I have been told that it is not uncommon now for a number theorist to have a hard time explaining the details of his work to someone who had specialized in analysis, much less to members of the "large audience of educated people."

Physics has had its share of prophets. If you care to learn more about one read "American Prometheus: The Triumph and Tragedy of J. Robert Oppenheimer." Superb book, winner of the Pulitzer prize.