The Winter semester just ended here in Kaiserslautern and I gave the last lecture of the Concurrency Theory course I taught. We covered Petri nets, WSTS and Process Algebra, exploring their theory with the underlying goal of automatic verification.

In the middle of the course, I realised that there were times where the students were slightly disoriented by the change of register when changing topic. To help them follow better, I came up with a simple notion that helped guiding them to pay attention to the right details. What I believe was causing the disorientation was what I called a switch from problem solving mode to conceptual mode. I think making this difference explicit and declaring when I was making the switch helped my student follow the line of reasoning more tightly. But I believe these two modes of thinking also help understand why Computer Science is rightfully considered to be part of the Natural Sciences.

Problem Solving mode: the Art of the Lemma

A lot of results in Theoretical Computer Science rely on hard combinatorial insights. As a consequence, the depth of a result in TCS is often related to the difficulty of this combinatorial core of the argument. Some researchers refer to this core as the “meat” of a result.

When trying to come up with this kind of results, or trying to understand them, the mindset one adopts is what I call the problem solving mode, that is, your attention is directed to details of the mechanics of a formally well-defined problem, a “puzzle”. An instance of a puzzle could be “How long can the minimal covering paths in a Petri net be?”.¹

This mode of thinking is the main one used in engineering work: you are presented with a complicated but circumscribed problem and apply some mathematical insight to provide a solution. In CS, the puzzles we face range from the very practical (“How do you sort an array as quickly as possible?”) to the very abstract (“How do you reduce the halting problem to a problem in arithmetic?”). But at the core, they require a similar mindset to find a solution. I would call problem-solving the “Art of the Lemma”.

Worthwhile puzzles are however never formulated in a vacuum: they arise as milestones in a wider conceptual framework that motivates their relevance and allows them to be defined in the first place. The activity of coming up with such a framework requires the use of what I call conceptual mode.

Conceptual mode: the Art of the Definition

Problem solving mode is what makes many put CS and Engineering together in the same category. I would argue that CS as a whole, sets itself aside from pure Engineering because of its substantial use of what I call conceptual mode. This mode of thinking is characterised by the exploratory experimentation with some basic phenomenon that we are trying to understand. The conceptualisation process works by formulating rigorous models of the phenomenon at hand and putting these models to test. It heavily involves abstraction, formalisation and generalisation abilities. The outcome of the process is a set of basic assumptions and definitions that would form the basis for a language to express facts and properties regarding the phenomenon under study. I would call conceptualisation the “Art of the Definition”.

Problems that are solved by employing the conceptual mindset are typically not well-defined and ambiguous. Examples could be “What is behaviour?”² or “What does it mean for an analysis to be sound?”.³

Big tech companies like Google or Facebook have interview processes set up to test the purely problem-solving abilities of candidates. Their reputation then does the rest: the problem solving aspect of CS is often over-emphasised and CS may be reduced to puzzle-solving from the perspective of an outsider. This makes sense if you consider that these companies are looking, most of the times, for Software Engineers. But in a University we aim at forming professionals that are prepared both technically and culturally. Only a balance between the conceptual and problem solving aspects of our discipline can achieve this.

Zen in the Art of Research

The two modes are both absolutely essential in solving typical CS problems. They are not competing but simply complementary. I find that making the switch between the two modes a conscious process, helps focusing on the important aspects of the problem and coming to a solution in a more enlightened way.

Conceptualisation provides direction and a strong relation with the phenomenon under study, producing puzzles that are not meaningless tricks. Problem solving gives depth to conceptualisation, allowing non-obvious consequences to be drawn from the premises.

If I think of the state of mind when doing conceptual work, I am reminded of the very nice description of the process of shooting an arrow in the book “Zen in the art of archery”, by the philosopher Eugen Herrigel. Although the book has many limitations, I still appreciate the attempt of the author to communicate to a Western audience ideas grounded in assumptions so distant from ours. Anyway, the description of the state of mind when shooting an arrow resonates, I think, with what one frequently experiences when doing research. The almost obsessive search for the right shot done in the training, striving for a liberation from preconceived assumptions, or emotional attachments to a dead-end. Then the moment of enlightenment: The Definition flows finally in a shape that feels right. And lemmas start to fall into place. The arrow leaves the bow and hits the target. Once The Definition has been produced, it may result completely obvious to the authors and even obvious to the readers. But this should not fool them: the path leading to its formulation was not obvious at all and to really appreciate its depth the reader must often go through the same path him/herself.

Computer Science is a Science

One may argue that Theoretical Computer Science is actually a branch of Mathematics and as such is not related to the Natural world in the same way as Biology or Physics are. I disagree with this position: the subject matter of CS is information and computation. Both are essential aspects of natural phenomena: every time we witness a computation in the physical world we are putting the theories of CS to the test. In fact this can be traced back to the beginning of CS as a discipline, which was marked by two complementary discoveries: the conceptual framework of computable functions and the technical possibility of testing this framework with computers.

Pure problem solving is essentially Engineering. Pure conceptual mode is Philosophy. Computer Science hits that sweet spot in between the two: it is the combination of the two modes that gives the discipline the relevance and depth of a Science.