Even though “computer science” has “science” in its name, some people, even some computer scientists, do not call computer science a science. So is computer science really a science? Or is it a branch of engineering, mathematics, or philosophy?

The main goal in this post is present what computer science is about and what the role of theoretical computer science is within computer science.

We’ll start with the following motivational quote.

Computer science is no more about computers than astronomy is about telescopes.

If computer science is not about computers—as in our laptops, tablets, and phones—what is it really about? To answer this question, we will compare another field, physics, to computer science. And then we will compare the role of theoretical physics within physics to the role of theoretical computer science within computer science.

A common pattern in many scientific fields, including physics, is the following. Given something we want to understand better in the real world, we first create a mathematical model that captures the essence of it. This is the modeling phase, which takes us from the real world to the abstract, mathematical world. Once we have a mathematical model, we can reason about it logically to derive new knowledge about the model. This gives us a deeper understanding of what we are studying. We come back to the real world in a couple of ways. First, we test the accuracy of our new knowledge through real world experiments. Second, assuming our model is accurate, we make use of our new understanding by applying it in threal world, creating new tools and technologies in order to make our lives better (and perhaps sometimes worse).

This summarizes one of the best methods we have for creating reliable explanations and knowledge using mathematical modeling and reasoning. A field that beautifully exemplifies the power of the above approach is physics. In physics, we try to understand the fundamental properties of matter, space, and time, among other things. And we have two amazing mathematical models that explain how our universe works: Einstein’s theory of general relativity, which models gravity and the behavior of large objects, and quantum field theory, which models the behavior of very tiny particles like electrons and photons. These two theories have revolutionized our understanding of the universe.

What is the role of a theoretical physicist (like Einstein or Hawking) in this picture? Theoretical physicists, based on experimental results, observations, and prior understanding, create new models. They also work with existing models to derive new consequences and knowledge from them. Primarily, a theoretical physicist lives in the mathematical/abstract world.

Computer science has a similar picture. In computer science, we study computation.

In its most general form, we can describe computation as manipulation of information/data. We’ll call the thing that does manipulation of information a “computer,” but we won’t restrict ourselves to laptops and phones, and keep the general description in mind. Usually, there is some input data that goes into the computer, the computer manipulates that data, and then produces output data.

This picture of computation is a bit vague, so to help us understand it better, let’s consider calculation. We can think of calculation as manipulation of numerical data (from basic arithmetic operations to calculating the trajectories of space capsules). But numbers are only one type of data. And we can imagine processing other types of data, like text, images, or videos. So computation can be viewed as a more general kind of calculation, the kind of calculation that you can do on arbitrary data. This distinction between calculation and computation actually turns out to be artificial (since arbitrary data can be encoded using numbers). But it is still useful to think about computation as generalization of calculation.

Let’s now mention some examples of computers. One obvious example is a calculator. By pressing a calculator’s buttons, you give it the input data. For instance, you may do 1 5 x 2 5 1 =. Then the calculator processes that information and produces the output 3765. An interesting question is “HOW does the calculator actually compute the product?” Does it contain a huge lookup table that stores the product of every two numbers that could be provided as input? No! The calculator runs a multiplication algorithm, which specifies a series of data manipulation operations to produce the correct output, for any possible input.

Another rather obvious example is the laptop or desktop computers that many of us use on a daily basis. These are called computers for good reason. At the lowest level, these computers store information as \(0\)’s and \(1\)’s, and there are circuits that manipulate that data to produce the output we see, say on the computer screen.

How about a human being or another organism? Given how we have defined computation, can we say that humans do computation? The answer is an emphatic yes. We take in information through our \(5\) senses, our brains process that information, and produce output information resulting in muscle movements and other activities in our body that we are not even conscious of. In fact, if you were to look up the word “computer” in a dictionary, you would find two definitions. The first definition describes an electronic device. The second one describes a person who does calculations. And indeed, in the early 20th century, before modern electronic computers were built, a computer referred to a person, not an electronic device. Computers were people trained in executing an algorithm to solve computational tasks.

How about a natural process like biological evolution? Can it be viewed as computation? Absolutely! When a species evolves and changes over time, it is the result of the genetic information changing over time. And this kind of change in information is a computational process.

These examples, and many others, illustrate that computation is a general phenomenon that can be observed almost everywhere. In many systems—whether natural or human-made, primitive or emergent—an important aspect of the system is how information evolves. This means that in many areas of interest, like physics, biology, chemistry, neuroscience, economics, finance, linguistics, statistics, social choice, etc. systems can be studied using the tools of computer science. The computational lens adds a powerful methodology for creating new knowledge and understanding.

Let’s now zoom in on theoretical computer science. Just like we can think of theoretical physics as the intersection of physics and mathematics, we can think of theoretical computer science as the intersection between computer science and mathematics.

In computer science, we want to study and understand computation. For this, we first build a mathematical model for it. Once we have a mathematical model, we can study computation in a rigorous way. We explore the logical consequences of our model and we prove theorems about it. These insights allow us to understand computation better and come up with good explanations for computational phenomena. Some of our insights lead to interesting applications, and we come back to the left-hand-side of the diagram by implementing those applications.

Computer science is extremely rich when it comes to applications. And most of the discussion about computer science is dominated by the amazing applications. Therefore it is not surprising that a lot of people view computer science as engineering. That is not wrong. Computer science is certainly engineering. But also, at its core, it is a science.

When creating a model of computation, we may be interested in modeling a particular system and its properties. Or we may be interested in modeling computation in its full generality. The birth of computer science is Alan Turing’s 1936 paper that gives a satisfactory definition of general computation, which we now call the Turing machine model. Our belief that the Turing machine model is the “right” model for general computation is captured by the following statement known as the Church-Turing thesis.

Any computation that can be realized in the universe (only constrained by the laws of physics) can be simulated using a Turing machine.

Even though we believe this thesis, if we are interested in faithfully capturing the computational capacity of our universe, we ought to be talking about effecient simulations. This is because there may be an efficient process that we observe in the universe that takes, say, exponential time for a Turing machine to simulate. In this case, even though the Turing machine can do the computation, it cannot do it efficiently, and therefore it is not a faithful model.

Any computation that can be efficiently realized in the universe (only constrained by the laws of physics) can be efficiently simulated using a Turing machine.

We actually do not believe this statement is true. In particular, we do not believe that a Turing machine can efficiently simulate quantum systems. This does not mean that the thesis is fundamentally broken. There are quantum models of computation that go beyond Turing machines, and we believe they faithfully capture the computational capacity of our universe. This highlights a couple of important things. First, there are various models of computation that are interesting to study. Turing machines faithfully capture the electronic computers we use today, but we also want to physcially realize quantum models of computation and harness its advantages (e.g. in efficiently simulating quantum systems). Second, if we want to understand the computational capacity of our universe, we have to incorporate our understanding of physics. Our models have to be informed by our environment and what the laws of physics allow.

Once we have a model of computation that we care about, we can explore the kinds of problems or tasks that are computable, and the kinds that are not. We can define various notions of resources for computation (like time, space, randomness, quantum entanglement, etc.) and study what kinds of problems or tasks are efficiently computable with respect to those resources. We can study the relationships among different resources. We can compare different computational models with respect to computability and computational efficiency. We can model various other notions relevant to computation, like privacy, fairness, rationality etc. and try to understand algorithms with respect to these notions. And we can think about how all of these insights can be used to deepend our understanding of other fields, create new technologies, and find new applications.

Let’s end this post by revisiting the questions we asked at the very beginning. Is computer science a branch of science, engineering, mathematics, philosophy, or something else?

Is computer science a branch of science? Absolutely. Computer science studies computation, which can occur both in natural systems and human-made systems. Information processing is a fundamental component of the universe we live in.

Is computer science engineering? Absolutely. A lot of the work done in computer science is about the amazing applications of the electronic devices that we use every day.

Is computer science mathematics? Absolutely. The way we rigorously study computation is through mathematical modeling and mathematical reasoning.

Is computer science related to philosophy? Absolutely. There are many interesting philosophical questions surrounding computation. For example, what does it mean to be intelligent? Can machines think, can they be conscious? Is consciousness related to computation? These are very interesting philosophical questions in the territory of computation.