This is a great article and I especially liked the notion:

>Theoretical physics is highly mathematical, but it aims to explain and predict the real world. Theories that fail at this “explain/predict” task would ultimately be discarded. Analogously, I’d argue that the role of TCS is to explain/predict real-life computing.

as well as the emphasis on the difference between TCS in Europe and the US. I remember from the University of Crete that the professors all spent serious time in the labs coding and testing. Topics like Human-Computer Interaction, Operating Systems Research and lots of Hardware (VLSI etc) were core parts of the theoretical Computer Science research areas. This is why no UoC graduate could graduate without knowledge both in Algorithms and PL theory, for instance, AND circuit design (my experience is from 2002-2007).

I strongly believe that this breadth of concepts is essential to Computer Science, and the narrower emphasis of many US departments (not all) harms both the intellectual foundations and practical employment prospects of the graduate. [I will not debate this point online; I'll be happy to engage in hours long discussion in person]

There is (mechanical/optical/*) engineering, experimental and theoretical physics, and then there is maths (focussing on physical problems). I think taking these four abstraction levels could be a model for computer science.

Now, theoretical physics is a bit of a troubled child however in recent years.

If we map computer science aspects in not the four physics disciplines, we get:

Software / hardware engineering

Applied computer science

Theoretical computer science

Mathematics dealing with problems inspired by computer science

> Theoretical physics is highly mathematical, but it aims to explain and predict the real world. Theories that fail at this “explain/predict” task would ultimately be discarded. Analogously, I’d argue that the role of TCS is to explain/predict real-life computing.

No this guy doesn’t get it. He doesn’t understand what science is.

In science nothing can be proven. If I say all swans are white as my hypothesis this statement can never be proven because I can never actually verify that I observed all swans. There may be some swan hidden on earth or in the universe that I haven’t seen. Since the universe is infinite in size I can never confirm ever that I’ve observed all swans.

However if I observe one black swan it means I falsified the entire hypothesis. Thus in science and in reality as we know it nothing can be proven… things can only be falsified.

Math on the other hand is different. Math is all about a made up universe where axioms are known absolutely. It has nothing to do with observation or evidence in the same way science does. Math is an imaginary game we play and in this game it is possible to prove things.

This proof is the domain of mathematics… not science. Physics is a science because it involves gathering evidence and attempting to falsify the hypothesis.

Einstein said it best: “No amount of experimentation can ever prove me right; a single experiment can prove me wrong”

Basically newtons laws of motion are a perfect example of falsification via experimentation with relativity later being confirmed as the more accurate theory that matches more with observation.

So what’s the deal with computer science?

First of all the term already hits the first nomenclature issue. Computer science is ironically not a science. It lives in the same axiomatic based world as mathematics and therefore things can be proven in computer science but not in science itself.

So this nomenclature issue is what’s confusing everyone. The op failed to identify that computer science isn’t actually a freaking science. Physics is a science but computer science isn’t.

So what is computer science? Sorry to say but it’s a math. I mean it’s all axioms and theorems. It’s technically math.

CS is a math in the same way algebra and geometry is math. Physics is a science and it is not a math. It’s a totally orthogonal comparison.

Your job as programmers is more like applied math. It’s completely orthogonal to the whole topic but People often get this mixed up. They start thinking that because programming is applied computer science then computer science itself is not a math.

Applied math ironically isn’t really math in the same way writing isn’t a pencil. Yes you use a pencil to write but they are not the same. Same thing with computer science and programming.

> In science nothing can be proven.

Asking here because it is mostly on-topic: This phrase is repeated often, but shouldn't it actually be, "In science, a hypothesis is either fundamentally verifiable or fundamentally falsifiable, but never both"? The two simply being the logical negation of each other.

"All swans are white" is fundamentally falsifiable (by seeing a black swan) but not verifiable, as you described.

"Black swans exist" is fundamentally verifiable (by seeing a black swan), but not falsifiable.

> Theoretical physics is highly mathematical, but it aims to explain and predict the real world. Theories that fail at this “explain/predict” task would ultimately be discarded.

Still waiting for theoretical physics to discard string theory, as it fails in predicting anything.

I met the author informally once but didn't know "who" he was, a famous academic scientist and professor etc. He read my paper and caught a math typo. :)

Regarding the article, I feel like there's some context missing, is this part of some ongoing debate about TCS? The piece abruptly ends.

One that comes to mind is the recent breakthroughs in AI which have caught theorists flat-footed. Sanjeev Arora and others openly admit we don't have a good theoretical understanding of the empirical successes of deep learning, how they are able to do the things they do with emergent phenomena, scaling effects, etc.

Scott Aaronson has also suggested that theoretical CS should be seen as analogous to theoretical physics.

On the other hand, I don't know if the argument could be abused to dismiss things like P vs NP as having no realistic scientific value. That would be the flip side of Vardi's argument. I do vaguely recall Aaronson in one of his blog posts or pdf essays* giving a more subtle argument about why P vs NP is central to computer science anyways, and I think that would be a slightly different position than either Vardi's or his reading of Widgerson's here.

*See the first several subsections about common Objections in pp 6-7 in: https://www.scottaaronson.com/papers/pnp.pdf

Ah, Professor Vardi, a fascinating case study in our department. His devotion to the 'science' in computer science is truly something to behold. It's not every day you see someone try to reconcile Turing machines with the second law of thermodynamics ...

Dr. Vardi's Second Law of Thermodynamics for boolean SAT and SMT (Satisfiability Modulo Theory) solvers is truly a marvel of interdisciplinary ambition. In his framework, computational entropy is said to increase with each transition of the Turing machine, as if bits themselves somehow carry thermodynamic weight. He posits that any algorithm—no matter how deterministic—gradually loses "information purity" as it executes, much like how heat dissipates in a closed system. His real stroke of genius lies in the idea that halting problems are not just undecidable, but thermodynamically unstable. According to Dr. Vardi, attempts to force a Turing machine into solving such problems inevitably lead to an "entropy singularity," where the machine's configuration becomes so probabilistically diffuse that it approaches the heat death of computation. This, he claims, is why brute-force methods become inefficient: they aren’t just computationally expensive, they are thermodynamically costly as well. Of course, there are skeptics who suggest that his theory might just be an elaborate metaphor stretched to breaking point—after all, it’s unclear if bits decay in quite the same way as particles in a particle accelerator.

I have to say that reading this from a non expert point of view leaves me wondering if this comment is true or if it is just the result of some elaborate prompt on ChatGPT

> Thinking of theoretical computer science as a branch of mathematics is harmful to the discipline.

Maybe the issue is how he thinks about mathematics... He quotes Von Neuman saying:

> We should remember the warning of John von Neuman,e one of the greatest mathematicians and computer scientists of the 20th century, regarding the danger of mathematics driven solely by internal esthetics: “There is a grave danger that the subject will develop along the line of least resistance.”

But for example, there is an article in Quanta [0] about a recent proof in Number Theory (you cannot get more "mathematical" than that), and the guy who proved it said:

> “Mathematics is not just about proving theorems — it’s about a way to interact with reality, maybe.”

Which is in line with Von Neuman's quote, and with the spirit of what the author is saying.

So maybe a more accurate subtitle would be:

"Thinking of theoretical computer science as a mathematical formal system is harmful to the discipline."

[0] https://www.quantamagazine.org/big-advance-on-simple-soundin...

For nature we have many models, physics, chemistry, biology, ..., depending on our needs. None of them are more wrong, but they operate at different scales and are useful in different contexts.

My gripe with theoretical computer science was that if felt like a Newtonian physics level model of digital processes, while an equivalent of biology level models would be needed for/suited to most "real-life computing".

A biology level model for computing would be some billion of very small CPU cores each one doing its own thing, interacting with the others (actor model?) and yielding a collective result by averaging their states (by some definition of average.) It could be OK for some problems (simulations of physical systems?) but not much for others (placing a window in the middle of the screen.)

By the way, a lot of small CPU cores is what we use inside graphic cards. However they are not actors. They are very deterministic. The Newtonian physics model.

How about we start by introducing time, interactions with things exterior to the subsystem modeled?

Well, that’s basically what we have with applications, isn’t it? It’s not like we need to think about each bit-trick we rely on when making a visio in parallel of a pair programming session over whatever IDE of the day we might use.

But how is that supported by TCS?

>“There is a grave danger that the subject will develop along the line of least resistance.”

What does von Neumann mean here? Why is it bad that it will develop along the line of least resistance? Does von Neumann advice that working on "harder" problems is more beneficial for TCS? Could not one argue that we should be solving away low hanging fruits first?

I am not sure if I am understanding von Neumann's quote nor this article properly. I would love to hear some simpler explanation (I am a new BSc. CS graduate).

This is how I see it: you can work on mathematics from two different levels. There is more direct level, which is the formal system, and there is more indirect level which are the intuitions behind the formal system.

If you look at new theories (let's say you are starting to study topology, or group theory) they start from some definitions/axioms that seem to come from "nowhere", but they are in fact a product of working and perfectioning a language for the intuitions that we have in mind. Once we set for the correct descriptions, then there are a lot of consequences and new results that come from interaction almost entirely with the formal system.

The interactions with the formal system is the path of least resistance.

The power of mathematics is that once you figure out a correct formalization of the intuitions, using just the formal system allows you to get a lot of information. That is why sometimes people identify mathematics with just the formal system.

To take it one step further, mathematical ideas which do not nicely fit within one of the highly developed theories then feels underbaked and less attractive to other mathematicians.

Knuth thinking about algorithms led to all these research questions about combinatorics, that have turned out to be very interesting, but are much more messy and disjointed results.

He says he affiliates a bit with physics. That is what I studied when I was young. Yes, physics attempts to concern itself with the real world. For instance, nobody in their right mind would have anything to do with quantum mechanics if it wasn't how the real world operated. In that sense it seems to me that computer science is much closer to mathematics. The computer is an artificial system constructed to be relatively easy to reason about.

Some people really like the math of quantum mechanics for its own sake.

(See also how (much of) the math for General Relatively was developed without any application in mind.)

'Liking for its own sake' is not quite enough. The first question is whether quantum mechanics would have been invented in the first place if it wasn't for experiments that showed that it was necessary. The second question is even if it was invented, would anyone bother to study anything beyond a single particle wave function? A wave function by itself is not yet quantum mechanics, there is quite a bit of wave mechanics in classical physics. I am quite sure that if quantum mechanics was not necessary nobody would attempt to say anything about a quantum mechanical carbon atom. I.e., a quantum mechanical six body problem. Let alone quantum field theory.

General Relativity much more natural than quantum mechanics. It was mostly created from a theoretical motivation. People were dragged towards quantum mechanics kicking and screaming and it took about 30 years to develop.

The Turing machine is an artificial system constructed to be easy to reason about. The computer on my desk is most certainly not!

Well, it depends. Have you ever considered writing a word processor in a Turing machine?

I like thinking of CS theory as "math, with more hand-waving". Or, I can't remember where I read it, but something about CS being the mathematics of asymptotes.