Does Computer Science Need Computers?

The pioneering computer scientist Edsger Dijkstra, winner of the 1972 A.M. Turing Award and inventor of one of the most iconic algorithms in all of computing, was nothing if not opinionated. Certain programming languages drew his ire, for example: He once dubbed Fortran “the infantile disorder” and stated that “the use of COBOL cripples the mind; its teaching should, therefore, be regarded as a criminal offence.” In justifying his disdain for using computers in his own work, he wrote, “Medical researchers are not required to suffer from the diseases they investigate.”

I first encountered Dijkstra’s hot takes nearly four years ago, not long after I joined Quanta as a staff writer covering computer science. The subject was new to me — I’d been a physics journalist, and before that a physicist — and I soon learned that most people don’t know how to interpret “computer science writer.” In the broader public discourse, computer science is practically synonymous with programming or coding, but at Quanta we cover the less understood theoretical side of the field. Then I stumbled on my favorite of the many memorable declarations attributed to Dijkstra: Computer science is no more about computers than astronomy is about telescopes.

This analogy, it turns out, may not have originated with Dijkstra, but he probably would have endorsed the sentiment. For me, the quote offered a pithy, provocative way to distinguish my reporting from tech journalism. And I can’t deny that it was flattering: The field I cover, it suggested, is about something deep and timeless and beyond mere technological innovation.

I got into the habit of invoking the analogy regularly — including in an episode of The Quanta Podcast — but I also began to have second thoughts about it, for reasons I couldn’t quite articulate. Was I just feeling guilty about an implicit dig at my former colleagues who build telescopes, or was the analogy missing something important?

I decided to try to get to the bottom of this. Is computer science about computers? And if not, what exactly is it about?

I was wading into a very old debate. Researchers began developing a mathematical theory of computation in the 1930s. Engineers built the first general-purpose electronic computers in the 1940s. Computer science emerged as a distinct academic discipline in the following decades, when the research traditions of math and engineering came together, and arguments about the nature of the new field soon followed. In 1967, the prominent computer scientists Allen Newell, Alan Perlis, and Herbert Simon staked out their position in a spirited letter to the editor in the journal Science. “Wherever there are phenomena, there can be a science to describe and explain those phenomena,” they wrote, with perhaps a hint of exasperation. “There are computers. Ergo, computer science is the study of computers.”

Newell, Perlis, and Simon addressed their letter in part to critics who argued that any science worth the name must study natural phenomena. They countered with examples of artificial phenomena considered worthy of study in well-established sciences, such as chemistry. In his 1969 book The Sciences of the Artificial, Simon went further and embraced the distinction: A focus on intentionally designed artificial systems, he argued, was precisely what made computer science special.

In 1974, the computer scientist Donald Knuth offered a distinct view of the field that emphasized the process of computing rather than computers themselves. He defined computer science as the study of algorithms, or precise step-by-step procedures, which computers use to accomplish tasks. Algorithms can be implemented in different programming languages, in much the same way that ideas can be expressed in English, Mandarin, or Arabic. Humans use algorithms too, not just to solve math problems, but also for tasks like sorting items. From this perspective, the math underlying computation is central; computers themselves are relevant only because they open up problems that we humans have neither the time nor the patience to tackle on our own.

Knuth’s definition is appealing to me, but it’s hard to deny the simplicity of the one offered by Simon and his colleagues. Yet neither these nor any other definitions seem to have achieved universal acceptance among researchers. Why is that? I asked William Rapaport, an emeritus professor of computer science and philosophy at the University at Buffalo, who has extensively chronicled the many proposed definitions of computer science. He suggested that the disagreement ultimately stems from the unusually interdisciplinary origins of the field.

“Computer science has two parents,” he told me. “It’s got a mathematical parent, and it’s got an engineering parent, and it’s really a cross between those two.”

Rapaport still sees a kind of intellectual unity in the field — it’s more than just math and engineering in a trench coat. Computer science, in his view, is the study of two central questions, which each subfield addresses in its own way: “What can be computed, and how do you compute it?”

I found this framing helpful. There are obviously branches of computer science in which computer hardware and software are essential, such as the design of operating systems or the study of memory management. But I’m ultimately most interested in the theoretical side of the field, where researchers need not ever touch a real, physical computer. Do computers play an essential conceptual role in this theoretical work? That’s what I’d need to investigate if I was going to sort out my mixed feelings about the Dijkstra quote.

Let’s start with Rapaport’s first question: What can be computed? To even begin to answer this question from a theoretical point of view, you need to start with a mathematical formalization of computing — what researchers call a model of computation. In the 1930s, researchers proposed several distinct models of computation and began to study their implications.

Then, in a famous 1937 paper, the mathematician Alan Turing devised a model based on hypothetical machines that could read and write symbols printed on an infinite tape according to a set of simple rules. Turing and others soon proved that this highly influential “Turing machine” model was mathematically equivalent to models proposed by other researchers. Suddenly, instead of several distinct definitions, researchers had a single, universal theory of computation.

Yet Turing’s theory of computation wasn’t really about computers, at least not at first. When Turing wrote his seminal paper, not only did he not have a general-purpose computer, he wasn’t even motivated by a desire to understand how such future machines might work. Rather, he was trying to solve a central problem in the foundations of mathematics. He viewed his machine as a way to model the mental activity of a human doing calculations.

What’s more, the theory of computation is broadly applicable to things we wouldn’t recognize as computers. Researchers often study natural processes by modeling them as computations and analyzing them mathematically. They’ve used this computational lens to expose unpredictable behavior in physical systems, analyze evolutionary dynamics, and attack puzzles in quantum gravity, among other applications. Ironically, the field that Simon hailed as a “science of the artificial” back in the 1960s is now central to our understanding of the natural world.

“You can view the other sciences through computation,” said Tom Gur, a theoretical computer scientist at the University of Cambridge. “It’s this underlying logical pattern that manifests itself pretty much everywhere.”

The answer to Rapaport’s first question seems to leave Dijkstra’s quote in a good place. And then there’s Rapaport’s second question: Once you’ve decided you want to compute something, how exactly do you do it? To theoretical computer scientists, the answer lies in the math of algorithms. In the late 1960s and early 1970s, they began to build a framework to quantify the time that algorithms require to solve different problems, at an abstract mathematical level that avoids all the details of computer hardware.

They soon came to appreciate that there are important qualitative differences among problems that might arise in practical applications, such as planning routes through networks and factoring numbers. All of these problems could, in principle, be solved by algorithms. Yet only some had clever algorithms that could produce a solution quickly. For others, the only known algorithms were painfully slow. Attempts to get to the root of these differences marked the beginning of computational complexity theory, the subfield of theoretical computer science that studies the inherent difficulty of different problems, and provides the basis for modern encryption schemes.

“Mathematical problems have a fundamental structure which makes them qualitatively easier or harder to solve,” said Cristopher Moore, a theoretical computer scientist at the Santa Fe Institute. “It’s not a matter of how fast your computer is, and it’s not a matter of how clever you are.”

If math is, in some sense, the language of reality, then mapping out this hidden structure can feel “like discovering the laws of the universe,” as the complexity theorist Valentine Kabanets of Simon Fraser University in Canada put it, when I spoke to him a few years ago for a brain-bending story about the most famous open problem in complexity theory.

Later developments in complexity theory pointed in directions that seem even less related to computing. As an example, Gur pointed to new notions of mathematical proof that emerged from complexity theory in the 1980s and 1990s. By reimagining proof as an interactive process, theoretical computer scientists discovered that it’s possible to prove that a statement is true without revealing anything about why it’s true, and that it’s possible to verify that certain proofs are correct by only checking a few tiny snippets.

“We suddenly come up with entirely new types of questions,” Gur said. “We say something which goes way beyond computation.”

To me, this all adds up to a compelling vision of computer science without computers. “There were fundamental questions here that could have been asked hundreds of years ago,” said Scott Aaronson, a theoretical computer scientist at the University of Texas, Austin, who’s also a member of Quanta’s advisory board. “It’s just that no one thought to ask them.”

Of course, that just raises another question — why not?

At least one person did think to ask those fundamental questions. The 19th-century polymath Charles Babbage, who conceived of a general-purpose calculating machine that he called the Analytical Engine, speculated in his autobiography that his new machine would call for a new theory of algorithms to go with it. “Whenever any result is sought by its aid,” he wrote, “the question will then arise — By what course of calculation can these results be arrived at by the machine in the shortest time?”

Babbage never completed his Analytical Engine, and it’s not clear exactly how he planned to address that important question. Perhaps he imagined that technical details of the machine’s design would make some methods faster than others; there’s no evidence that he anticipated anything like the rich mathematical structure that complexity theorists have since discovered.

But that, it seems to me, is precisely the point. The central question in complexity theory, about why some problems don’t seem to have fast algorithms, may not look very profound at first glance. Its depth only becomes apparent when you start to explore it — and it wasn’t until researchers started playing around with real computers in the 1960s that the question seemed worth exploring.

I think this is ultimately what’s missing from a picture of computer science that downplays the role of computers: In the historical record, deep theoretical questions are often intertwined with practical ones about building better machines.

Matti Tedre, a computer scientist at the University of Eastern Finland and the author of a book about the disciplinary identity of the field, isn’t a fan of the Dijkstra quote as it’s usually understood. Even so, the comparison to astronomy may be apt in another way.

“[Dijkstra is] absolutely right; it’s just that he’s wrong about the importance of telescopes to astronomy,” Tedre said. “We wouldn’t know a thing about the universe if we didn’t have telescopes.”

Beyond the field of computer science, there are lessons here for how we think about scientific progress in general. In one common view, breakthroughs in pure science spur advances in technology: Think quantum physics leading to the transistor, or relativity enabling GPS. The history of computer science suggests a more nuanced interplay between the profound and the practical, one that also has parallels in other disciplines. Aaronson pointed to the second law of thermodynamics, which states that entropy, a measure of disorder, tends to increase over time.

“It’s maybe the most fundamental thing that you can say about the evolution of the entire universe,” he said. “And yet it’s not something that anyone thought of until they were building steam engines.”

Or, as the complexity theorist Ryan Williams of the Massachusetts Institute of Technology put it, “Sufficiently interesting problems in practice generate great theoretical questions.”