What is Computer Science?

In 1961 George Forsythe proposed to establish a department of “Computer Science” at Stanford University. The quotes are here on purpose, because at the time the concept was new. Even now there are those who question whether there is a concept rather than just an incongruous juxtaposition of two words. Such people are apt to snigger “telescope science”, with the message that astronomy is real science.

Donald Knuth defends the concept thus [1]:

There are different flavors of mathematics, based on what kinds of peculiar minds we have; we aren’t going to change that. People find out what things are best for them. And as for their mentalities, physicists are different from mathematicians, as are lawyers from doctors. Each of these fields seems to have predominant modes of thinking, which people somehow recognize as best for them. Computer science, I am convinced, exists today in universities because it corresponds to a mode of thinking, a peculiar mindset that is the computer scientist’s way of looking at knowledge. One out of fifty people, say, has this peculiarity.

It’s a bit disconcerting that Knuth’s estimate of two percent reflects his experience teaching classes in Stanford’s Computer Science department. The probability of hitting your vocation right away is not high, consistent with my own experience. We can only hope for the remaining ninety-eight percent that they will find it on their next try. Knuth continues with:

Historically, such people were scattered in many walks of life: we had no home to call our own. When computer science started out it was mostly treated as a tool for the existing disciplines and not of interest in its own right. But being a useful tool is not enough in itself to account for the fact that computer science is thriving in thousands of places. For example, an electron microscope is a marvelous tool, but “electron-microscope science” has not taken the world by storm; something other than the usefulness of computers must account for the rapid spread of computer science. What actually happened was that the people who got interested in computers started to realize that their peculiar way of thinking was shared by others, so they started to congregate in places where they could have people like themselves to work with. This is how computer science came to exist. Now we can look back in old writings and see that certain people were really computer scientists at heart. It was latent back in Babylonian times, and throughout history.

Those “certain people” were not really “from all walks of life”: they were mathematicians. And indeed mathematicians come in many varieties. One gets a good idea of this variety when we collect some examples of mathematicians calling each other names.

Paul Halmos (1916–2006) is famous, among other things, for the article “Applied Mathematics Is Bad Mathematics”. At the end of his interview [1] he was asked whether he had anything to say on this topic. Halmos: “For the last 55 minutes I have been dreading this question.” Nonetheless, he proceeded to give illuminating comments on his controversial thesis. He closes with:

There is a sense in which applied mathematics is like topology, algebra, and analysis, but … there is also a sense in which applied mathematics is just bad mathematics. It’s a good contribution. It serves humanity. It solves problems about waterways, sloping beaches, airplane flights, atomic bombs, and refrigerators. But much the same, much too often it is bad, ugly, badly arranged, sloppy, untrue, undigested, unorganized, and unarchitected mathematics.

Halmos sees logic as especially good mathematics. Elsewhere in the interview Halmos explains that there are levels of mathematics. Applied is lower than the main body of mathematics. Mathematical logic he considers higher. My guess is that category theory would also be recognized by Halmos as being in the higher part. It is no coincidence that mathematical logic and category theory are rejected by many mathematicians as not really mathematics. And these parts of mathematics happen to be especially useful in computer science.

Graph theory has famously been called “the slum of topology”, point-set topology and combinatorial topology being the more chique varieties. Though hackneyed, for our purposes the slum thing is useful: is it a coincidence that there tend to be more graph theorists in computer science than in mathematics departments? Combinatorics has been decried as a “grab-bag”. Not so chique either, and common in computer science departments. Knuth, thirty-five years after Volume Three, has started to publish bits of Volume Four, Combinatorial Algorithms, and in the preface he confesses to liking these best of all.

In the 19th century Paul Gordan played around with systems of invariants for polynomial forms. He was admired for his ingenious constructions and lengthy calculations. As a result he conjectured that every such form has a finite complete system of invariants. “Hilbert proved in a few pages what many people doubted and Gordan had not proved in 20 years: they exist” [2]. The proof proved existence; it gave no clue about finding any. Gordan’s first reaction was reported to be “This is not mathematics; this is theology” [3]. Hilbert returned the compliment when Gordan died, saying: “He was an algorithmician [my rendering of Algoritmiker].” Guess who was the crypto-computer scientist.

In the late 1960s E.F. Codd wanted to improve information storage and retrieval by putting it on a mathematical basis. His proposal was to represent data as relations in the accepted mathematical sense. What Codd found as this “accepted mathematical sense” were relations as sets of tuples, where these tuples had numerical indexes. Mathematicians left it with this special case. They wanted to get on with whatever job they had in mind with a minimum of fuss. Codd adopted this definition as mathematical gospel. However, numerical indexes led to no end of trouble in the relational data model.

But there is nothing unmathematical with non-numerical indexes. In fact, Halmos in Naive Set Theory practically invites the reader to use any set you like as the index set of a tuple. A consequence is that the indexes have to be typed compatibly with the corresponding tuple values, a complication that can be elegantly solved with the beautiful mathematics of commuting diagrams. The details need not concern us here; what matters is that a little curlicue like this is a distraction to a mathematician on a major mission, but it may be of crucial importance in another discipline. Can we characterize computer science as the kind of mathematics that mathematicians are not interested in?

Knuth at least feels comfortable with mathematicians — after all, he was interviewed in Mathematical People [1]. E.W. Dijkstra (1930 — 2002), recognized by Knuth as a computer scientist par excellence, does not. In a conversation with him, he reminded me of the Dijkstra-Scholten approach to logic and asserted that mathematics should be done formally, using this system. This struck me as naive. I felt fatherly when I told him that I had shared his discomfort with mathematicians, but that there was a nice little book that cured me of mathematics envy; that after reading it I had become comfortable in the knowledge that there was no longer a hollow place in my head where mathematics should be.

“What book may that be?” Dijkstra inquired suspiciously. “Halmos’s Naive Set Theory“. Upon which Dijkstra exploded in indignation: “That is exactly what I mean!” He went on to explain that this was the example par excellence of the way mathematics was being taught in the informal way that students can only absorb by osmosis in one-on-one interactions between Master and Apprentice, just like in the medieval guilds. He shuddered at the medieval. Dijkstra wanted his mathematics formal, its methods explicit. He wanted programs to be a machine-readable kind of mathematics.

Knuth recognizes mathematics and computer science as requiring different ways of thinking. But so are chemistry and computer science. Isn’t there some special relationship that mathematics has to computer science that chemistry does not? Dijkstra would not only affirm this, but goes overboard by denying the right of mathematicians to have a different way of thinking. The truth is somewhere in between: computer science is mathematics, but much of it is the mathematics that mathematicians are not interested in. Mathematicians are suspicious of mathematical logic, category theory, graph theory and combinatorics. They feel it is border-line, without being concerned what is on the other side of that border.

I think I know what is there: Computer Science.

[1] Interview in “Mathematical People”, D.J. Albers and G.L. Alexanderson, editors, Birkhäuser, 1985.

[2] “Theology and Its Discontents: the Origin Myth of Modern Mathematics” by Colin McLarty

[3] Gordan’s second reaction was: “But perhaps theology has its merits.”

5 Responses to “What is Computer Science?”

  1. Daniel Lemire Says:

    Let me quote Doron Zeilberger :

    “The fate of Platonic mathematics is nowadays quickly joining the fate of Platonic, a priori, non-experimental, physics.”


    To translate: the type of mathematics mathematicians are “interested in” is less and less relevant.

  2. Andre Vellino Says:

    I know a highly respected number theorist (who shall remain nameless, lest he disapprove of what I say :-)) who believes the question P=NP is one of the most interesting and fruitful areas of mathematical research. Yet it’s a problem that was *defined* by computer scientists (Steve Cook) and goes to the foundations of mathematical logic *and* computability.

    I challenge Daniel’s remark that mathematicians are interested in is “less and less relevant”. Define “relevant”, Daniel! Relevant *when*? and *to whom*? For one thing, I think the time-scale of “relevance” in mathematics is quite different. It took 350+ years to solve Fermat’s last theorem. Is all the mathematics that went behind that “irrelevant”? How would you tell?

    What can I say? I still bow in reverence to the Queen of Mathematics and hold my number-theorist friend in awe.

  3. Narrow Says:

    This article presents a hugely narrow view of computer science and then defines
    it as “mathematics the mathematicians are not interested in”. There is so much
    wrong here that it defies any further response.

  4. australian iphone apps Says:

    Thanks for the nice post!

  5. Jakob Voss Says:

    Your definition only highlights a specific aspect of computer science, but a very interesting one, so thanks for article and for the references. To complete the picture, we should have more “what is computer science?” articles from other directions but mathematics, for instance (electrical) engineering and management. You could argue that only theoretical computer science is real computer science but than you limit it to problems that neither mathematicians nor anyone else is interested in. My main interest in computer science is also on the mathematical side, but I feel that without management and engineering you do not grasp the idea of the discipline.

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 )

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s

%d bloggers like this: