Wednesday, May 25, 2005

Durable metaphors for (theoretical) computer science

Michael Mitzenmacher writes:
I think as a field we need to do a better job clarifying that computer science is about a lot more than programming, and that the skills learned in the major can apply well in other areas.
Indeed. One of the main areas of discussion at the STOC business meeting appeared to be (I did not attend) on ways of disseminating the impact of theoryCS. The new theory advocacy website aims to be a clearinghouse of such information.

However, there is an important other angle to this whole business of demonstrating the value of theoretical computer science (and CS in general, although this post will be theory-centric). Not only do we need demonstrable examples of where theory is used in practice, but we also need a more fundamental story line for the raison d'etre of theory in the first place.

To take the example most commonly touted, the mythical 'man on the street' has probably heard of E=mc2 and quantum physics and something about relativity, without necessarily understanding anything more about it. This person, if asked, will be able to hazard some guess as to what physicists do, and how it's fundamental (in a vague way) to everything in our modern world (at least to nuclear weapons and space exploration).

But we don't have a similar story line for theoryCS.

The point of doing theoryCS is that one believes (and there are degrees of belief here) that a computation is a tangible entity. What I mean by this is that there is something almost Platonic about a 'hard' problem and an 'easy' problem; the intrinsic complexity of a problem appears to be a feature of that problem itself, independent (upto a point) of which machine we are using.
These statements are given their heft by the Church-Turing thesis and its effective variant, and even the notion of completeness, the idea that certain problems are the exemplars of what is hard to do with a certain limited resource.

I am uneasy going as far as claiming that there are 'natural laws' for computation, but the analogy is not completely outlandish. Theoreticians do believe that at the core of any computation is "a problem", and the first order of business is to identify this core problem and classify it depending on various measures of complexity (space, time, etc).

But this is not an idea that is conveyed in most undergraduate classes in computer science. In fact, this is not even an idea necessarily shared by all areas of computer science, otherwise we'd see a lot more 'problem identification and classification' than we currently do.

The idea though is crucial to providing a deeper answer to the 'whys' of computer science, in a way that can capture the imagination, far more so than a litany of applications. After all, let's face it; people don't remember general relativity and quantum physics for the list of applications enabled by them, but for an ineffable mysteriousness and beauty that surrounds these descriptions of our world.

We need to communicate that same sense of beauty that comprises the hard core of (theoretical) computer science if we want to convince people that the field is more than just programming. This is not as a replacement for the more traditional theory advocacy that we should and must do, but as a different form of advocacy that targets a very different audience, for a different purpose.

Disqus for The Geomblog