Theoretical Computer Science vs other Sciences?

Question

So I‘m in my fifth semester studying Computer Science at a German university, so I‘ve only scratched the surface of Theoretical Computer Science, namely Logic, Formal Languages, Automata Theory, Computability and Complexity.

I know some people doing physics and engineering, and I always get this funny feeling that what they learn is so much more important and so much more useful, than theoretical computer science.

Don’t get me wrong. There are many very very interesting topics in TCS and it seems to answer a lot of questions. And frankly, I really like it.

I recently saw a video of Richard Feynman (the famous physicist), in which he explains a bunch of physical phenomena. It’s on youtube, it‘s a famous one, and it completely blew my mind and it just got me so giddy and excited. And in that moment, I reflected on what I was learning on the theoretical side of my CS degree and I secretly thought to myself, it‘s all very elegant, but this is really just a bunch of abstract, fancy notation, for something, which in comparison to stuff like calculus, mechanics, quantum physics, is not really that impressive in what it‘s saying.

Of course, some famous consequences and implications of Theoretical Computer Science, like the halting problem, are completely mind blowing; it just doesn‘t seem to me, to happen as often, as in other subjects.

So when I think of topics like classical mechanics and analysis and the little I know about some of the more advanced topics, I can always think of so many ways to apply them to the real world, and their connection to problem-solving seems so much more mature, clever and intricate than what I‘m learning on the theoretical side of my CS Bachelors.

This is probably some weird form of imposter syndrome. Or maybe I‘m simply studying the wrong thing. Maybe the teaching at my university is bad, or maybe I’m just not studying enough. And I probably just wrote a bunch of nonsense, and simply don‘t know enough yet (obviously, I don‘t).

But do other undergrads have this feeling, too? It really feels like I‘m completely missing the big picture. Or is this really just a me problem?

Answer 1

As a theoretical computer scientist I am proud of the following achievements of the field.

1. Logicians figured out that all logical connectives can be build from a single one, paving the road for modern digital circuits.

2. Alan Turing invented the notion of a universal computing machine that could compute anything that could be computed. His ideas changed the meaning of the word computer, which used to mean "a human performing calculations".

3. John von Neumann, in cooperation with engineers, developed a computational model on which all modern computers are based.

4. Claude Shannon developed a mathematical theory of information whose applications extend beyond computer science, all the way to black holes.

5. Quantum computers were invented by theoreticians, of course.

6. Alan Turing invented artificial inteligence as a theoretical idea.

7. Alonzo Church invented the $\lambda$-calculus, on which functional programming langauges are directly based. (I am partial to this one, being Alonzo Church's academic grandson.)

Seven is a magic number, so I'll stop here even though it was not easy to select just a few, and the list is far from exhaustive.

It is safe to argue that these are comparable to some of the greatest achievements in other sciences, and that they have had deep and lasting impact on humanity.

Answer 2

As a TCS researcher, I understand the feeling and feel it too sometimes. I think it is healthy to be able to appreciate the wonder that other sciences have to offer.

We must also keep in mind that it is unfair to compare the gems relayed by Feynman with a cursus that you follow day-to-day, where the few magic moments can be overshadowed by the hard work and preliminary learning that you have to get through. It is a classic trap to believe that the grass is always greener elsewhere. I bet the daily practice of physicists is also mainly hard work and mundane tasks and that it's not easy to maintain a sense of wonder. Probably many of them envy the mathematicians who can delight in their world of pure thought without having to wait for the LHC to be available in 6 months for their experiment aiming at finding the 10th decimal of a physical constant.

That said, if you think that you are genuinely more interested in physics than TCS, you should take the time to consider switching cursus. It's hard to give more precise advice without knowing you, but if you consider that the halting problem is mind-blowing, I'd say TCS is at least one of the possible choices, and don't worry there's more where that came from :)

Answer 3

I run a small software business producing XML processing tools, so I'm very much a practical engineer rather than a theoretician. It's 50 years since I did my CS degree. And you know, I'm constantly wishing I were better at understanding CS theory. I'm constantly coming up against problems where I feel a better training in the theory would help me.

Of course there's a spectrum from theory to practice. I'm thinking primarily about stuff that a true theorist would consider rather practical, like algorithms for graph traversal or evaluation of regular expressions.

It's not really clear what your question is. Is theoretical computer science important? Sure. Is it what you're most interested in? Only you can answer that. Is studying theoretical computer science useful in later life? In my case, yes.

Answer 4

My impression from your comments is that perhaps you have just not seen enough theoretical CS to get to some of the kind of content you are excited about in, say, physics.

I'll also point out that you make two quite distinct remarks about the nature of the results: (1) "not really that impressive in what it's saying" and (2) applications to the real world, connections to problem solving seem less mature, clever, and intricate than what you see in (e.g.) physics. Your example of the Halting Problem being exciting seems to cover issue (1), but not so much issue (2). My answer also mostly focuses on issue (1).

Let me add a few more examples coming out of theoretical computer science that I think are quite deep philosophically about the nature of the universe - and what kind of information processing is possible in it - similar perhaps to how you feel about the uncomputability and universality of the halting problem.

1. Using randomness can help speed up processes where neither the input nor the output involve any randomness - randomness can act as a sort of "information processing catalyst"
2. On the flip side, if there are problems that are sufficiently hard to compute, then those problems can be used to fool polynomial-time algorithms into thinking they are using random bits when in fact they are fully deterministic. In this sense, we think randomness may not "help" more than polynomially much, but to do that, we have to prove strong lower bounds on the complexity of other problems. The key phrase to search for here is "hardness versus randomness". (Part of the hardness vs randomness results is that proving lower bounds is essentially equivalent to giving non-random simulation of all poly-time randomized algorithms.)
3. Public key cryptography. The very idea that two parties who had never exchanged a private, secret key before could nonetheless communicate and be virtually assured of the privacy of their communication seems to me like a pretty deep fact about the nature of information transmission and communication.
4. Zero-knowledge proofs. For certain kinds of facts (those corresponding to the complexity class $\mathsf{ZK}$ or $\mathsf{SZK}$, which includes many natural things like graph isomorphism and all of $\mathsf{NP}$), it is possible to prove to someone else that you know the fact without revealing to them anything about the fact itself, other than that you know it.
5. The very fact that so many computational problems that people want to solve are all equivalent to one another, and in fact are basically just re-encodings of one another (they are p-isomorphic, see the Berman-Hartmanis Isomorphism Conjecture and this related question). Let alone the fact that they are universal amongst combinatorial search problems (sort of like a "finitary/polynomial" analogue of the halting problem; indeed, a bounded version of the halting problem is $\mathsf{NP}$-complete). This one could arguably be a statement more about humans than "the universe" (though of course we are part of it!), but even as a statement about the kinds of problems that people are interested in, it strikes me as pretty surprising, deep, and interesting.
6. Formalizing the notion of "reduction", that one problem can be "reduced" to another, has been very fruitful, beyond in CS. I really like Gil Kalai's answer pertaining to this here

More generally, I think many complexity results have pretty deep philosophical interpretations. Along these lines, you might enjoy Scott Aaronson's "Why Philosophers Should Care About Computational Complexity"

Answer 5

Maybe I can offer some interesting point of view here: I finished my Bachelors degree in physics and started a bachelors degree in software engineering afterwards. People often ask me why, which the answer to is manifold. Firstly, discoveries in the field of physics are a lot of hard, unforgiving work. Work, where you do not have a clear and concise target. One person may lie to groundwork for bigger discoveries, but you often don't get to see them. The research community is one that compares your value to your discoveries or amount of papers you wrote. Secondly, and this might be biased, institutions try to kind of guilt trap you into staying for very little pay, because "your masters degree is not worth a lot without a Dr.".

Compare that to the computer science: When you start to fiddle with the complexity of algorithms and if something is even computable you very much are asking how powerful are our computers? The beauty here is that big steps are still possible. You will be able to work at the edge of what is computationally possible, which is a field vast enough in itself.

Understanding that everything works in conjunction together is also very important: Without physicists basic groundwork an electrical engineer would not have been able to engineer a computer. Without a low-level programmer we would not have proper efficient multi purpose computation units and without high-level developers those would be unused as well. Every field of science is interesting and beautiful in its own right and you sure as hell are allowed to dive into others. If you are interested visit that experimental physics class. It not contributing to your credits is in my humble opinion less important than you broadening your horizon.

Answer 6

I recently saw a video of Richard Feynman (the famous physicist), in which he explains a bunch of physical phenomena. It’s on youtube, it‘s a famous one, and it completely blew my mind and it just got me so giddy and excited.

Maybe it is interesting for you to hear that Mr Feynman also did research in TCS. He wrote a book Lectures on Computation and he layed some groundwork in quantum computation (he basically proposed the circuit model of QC).

For me, I got interested into CS because of the philosophical question of what is computable, and then, what is efficiently computable. Possibly, outside of the TCS & Logic "bubble" not many people really care about that.

really just a bunch of abstract, fancy notation,

Some people say this about quantum mechanics (QM) or mathematics. The initial years of QM are known for attempts to give epistemological meaning to the wave function and the nature of QM.

Answer 7

I have worked in IT for 27'ish years, and studied CS in Germany as well; even at a more theoretical uni (there was a separate "technical" uni in our city which got to do all the robotics stuff etc.). I got to use my knowledge from there at work quite seldomly, but still view it as a great base for my work.

In principle it is true, you can create software - certainly run-of-the-mill office / end-user software - without studying IT or Theoretical Computer Science. But the reason for that is not that CS is superfluous, but that the IT community has, in the last decades, transformed all we learn from (T)CS into manageable, usable little tools and methods which just work out of the box; so much so that many professionals, not even to talk of fresh students, know precious little of how all of it works under the hood anymore.

For example, take Data Structures as a more practical topic. There has been, and still is ongoing research in how to structure data for certain use cases. The fact that these days you have terabytes of data at your fingertips in the blink of an eye, literally, is only made possible through CS.

Networking, another more practical area of CS, is very relevant - it has strong crossover into electrical engineering for obvious reasons, but still. Things like border gateway protocols and so on still need to be made and improved over time. Check out Claude Shannon, an engineer in the more theoretical areas surrounding networking; with topics like bit encodings, fundamental theorems about information packaging etc.

Many advanced programming languages have been possible through advances in theoretical computer science directly - "languages" (not necessarily just in the meaning of programming languages) are the bread of butter there. Not only creating functional or otherwise advanced languages, but also thinking about correctness, complexity and so on.

Algorithms can usually at least partially be thought of as part of CS, even though they often are also partially anchored in their respective domain. It certainly helps to know many data structures and basic algorithms to be able to come up with good new ones.

Cryptography is very much a part of maths, but can certainly also be viewed through the lens of Theoretical CS. Without it, much of our current laissez-faire usage of services on our devices would not be possible.

The whole area of machine learning and what we call "AI" today (which certainly is artificial, if not necessarily intelligent in any way whatsoever ;) ) certainly can be counted to the tCS field as well.

TLDR: the fact that you are maybe reading this in your possibly cheap Smartphone, somewhere in the world; and that you are, at least in the developed countries, enjoying a standard of living like never before in humanity's history, is a direct output of Theoretical CS and the more practical IT sector that builds on it.

Answer 8

Back in college, I loved TCS for the mental gymnastics. I'd argue that, for better or worse, they shaped the way my mind works: I'm a decent programmer and, generally, technologist and I think that's in part due to the training I got from TCS homework.

However, these days, I'm thrilled about what I learned from those classes not so much for practical reasons, but for philosophical ones: IIRC, Turing himself described his work as modeling how a rational person would go about solving a problem. And that's, to a large extent, the same as modeling human thought. So, TCS can give you insights into how you and I think, and to me, that's really exciting.

Now, if you're having trouble relating what an NFA or even a Turing machine does to the blooming, buzzing confusion you find in your mind, I'll urge you to read some of the philosophers who are versed in CS as well as in the cognitive sciences. My favorites are Dennett (Consciousness Explained, definitely read in English) and Hofstadter (I am a Strange Loop).

Answer 9

There is a tension between theory and praxis in any discipline. In TCS, many ideas that are cooked up in labs as products of research and development eventually surface 20 years later in industry. When Turing, Church, Kleene and others created formalism for understanding effective computability, they were pioneering not just computer science, but the philosophy of computation (SEP). It may be hard to appreciate the contributions of TCS relative to "lumps of clay" like the laptop on your desk, but inevitably, big ideas in TCS become transformative in technology practice. It seems secure to say that Alan Turing's idea about computability helped win World War II given his contributions to Bombe and cracking Enigma. Remember, cryptanalysis is itself is theory, so cracking codes is all about having better computational theory, and Turing and a handful of thinkers simultaneously took the problem of calculating ballistic trajectories and cracking enemy ciphers and arguably fundamentally transformed computation and communication. It hasn't been 100 years since the first computer scientists (who were mathematical logicians) thought up some interesting ideas and now we find the planet is covered in conservatively tens of billions of microprocessors.

Sure, the physicists invented the atomic bomb, but which has had a bigger impact on the human condition, a nuclear explosive or the electromechanical computer? I'd argue the latter, and it's because of TCS. These days, TCS is looking at quantum computers and changes in how we perceive problems of computational complexity. In fact, TCS is still wrestling with the P-NP Problem, a problem so important, that it's recognized as one of the most pressing question of computation in the world (and has a tidy purse attached to it if you're interested). So, physicists have their thing, the universe, and mathematical logicians have their thing, mathematical systems, but computer scientists and TCS is the intersection of the two. It's not easy specifying and building computers de novo precisely because one has to understand both mathematical logic and physics to do so well.

Answer 10

It seems that your education has sparked (or noticeably deepened) your fascination for theory in general, a fascination you can experience and build upon in the field of TCS and could experience and build upon also in the field of theoretical physics, or mathematics, for that matter.

Unfortunately, you need to focus your studies somehow. Fortunately, you do not need to become a physicist in order to appreciate connections between TCS and physics that can perhaps convince you (and your friends from physics) of the fundamental nature of TCS in connection to physics.

Here is one connection I find interesting: Perhaps, a friend of yours from physics has wondered at some point why optimization problems (like energy minimization or the principle of least action) are so effective at describing natural phenomena. If they are casually interested in computer science, they may have wondered why this is true for the even narrower class of optimization problems whose constraints can be verified efficiently. Otherwise, they might find this question purely philosophical and perhaps inaccessible to mathematical rigor. As a computer scientist casually interested in physics, you may have asked yourself whether all finite natural phenomena are in the complexity class NPO. For the sake of the argument, let us assume that all natural phenomena are finite. Curiously, Fagin's theorem tells us that a positive answer to the latter question (are all natural phenomena in NPO?) would explain the effectiveness of optimization problems with efficiently verifiable constraints in describing natural phenomena.

Answer 11

Physicist here. I have three things to contribute to this discussion:

1. Firstly, the most exciting things happening in theoretical fundamental physics these days are all related to quantum information theory. It turns out that quantum gravity (in some ways the deepest fundamental theory of physics) has intricate connections to information theory. A major effort to understand these connections is the "It from Qubit" collaboration, which you can read about here.
   As a sample of ideas from this field: Black holes turn out to be essentially optimal information scramblers; black hole entropy is related to entanglement across the event horizon; the state of certain quantum systems in the interior of a region is encoded on the boundary of the region via a quantum error-correcting code.

2. I do fundamental physics with ultracold atoms. I spend about half my time working on algorithms for various problems, like partial differential equations, computational geometry, data analysis, etc.

3. In all fields of science, there's typically a wide berth between real applications and the "useless problems" that pure scientists enjoy thinking about. Scientists are often experts in a very narrow field and don't have any idea how it applies to the "real world". This could be seen as a defect of our education systems, or of the institutions that support our science, and it's true of physics, theoretical computer science, and most any other field of pure science.

If you want to understand applications to real world problems, you are unlikely to get that in academia; maybe try joining a startup instead. If you want to probe the deep questions of the universe, quantum information theory is a great option that involves both physics and theoretical computer science.

Answer 12

P vs NP is one of the most important questions in mathematics and it is at the heart of TCS.

It has tremendous practical and philosophical implications:

• Are all easily checkable theorems also easily provable?
• What is the true power of non-determinism? Is it inherent in our computational universe?

Moreover, the whole undecidability theory gives tremendous insights on the nature of computability and it does so unconditionally: proving that some physical quantity is uncomputable means that it remains uncomputable for any other alien civilization living, for ex., in Andromeda galaxy.

If these implications seem too modest to you, I am not sure what could possibly change your mind.