Computer Science Debates Its Core Subject

Theoretical computer science is engaged in a long-running debate over whether its core subject is computers or the abstract study of computation. The question, which dates to the field's formation in the mid-20th century, hinges on its interdisciplinary origins in both mathematics and engineering.

According to a report in Quanta, the debate was famously framed by computer scientist Edsger Dijkstra, who argued that "computer science is no more about computers than astronomy is about telescopes." This view emphasizes the mathematical foundations of the field over physical machines. However, in 1967, prominent researchers Allen Newell, Alan Perlis, and Herbert Simon countered this in a letter to Science, stating plainly, "There are computers. Ergo, computer science is the study of computers."

The Interdisciplinary Roots

William Rapaport, an emeritus professor of computer science and philosophy at the University at Buffalo, explained the disagreement stems from the field's parentage. "Computer science has two parents," Rapaport said. "It's got a mathematical parent, and it's got an engineering parent, and it's really a cross between those two." He sees an intellectual unity in the field centered on two questions: "What can be computed, and how do you compute it?"

This dual nature means some branches, like operating system design, are deeply concerned with hardware and software. Others, particularly theoretical work, can proceed without ever touching a physical computer.

What Can Be Computed?

The quest to answer Rapaport's first question led to foundational models of computation developed in the 1930s. Alan Turing's famous 1937 paper introduced a model based on hypothetical machines that read and write symbols on an infinite tape. Turing and others proved this "Turing machine" model was mathematically equivalent to other proposed models, creating a universal theory of computation.

Crucially, Turing was not motivated by a desire to understand future computers. He was trying to solve a central problem in the foundations of mathematics and viewed his machine as modeling the mental activity of a human doing calculations. Today, this theory of computation is applied to natural processes, from analyzing evolutionary dynamics to attacking puzzles in quantum gravity.

"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."

How Do You Compute It?

The answer to Rapaport's second question lies in the mathematical study of algorithms. In the late 1960s and early 1970s, theorists built a framework to quantify the time algorithms require to solve problems at an abstract level, avoiding hardware details. They discovered important qualitative differences among problems. While all could be solved by algorithms in principle, only some had clever, fast solutions. Others required painfully slow procedures.

These investigations marked the beginning of computational complexity theory, which studies the inherent difficulty of problems and provides the basis for modern encryption schemes. This theoretical work, central to understanding what can be computed efficiently, often proceeds without direct reference to physical computers, further complicating the simple definition of the field's subject.