12 ms·

What is theoretical computer science?

167 points by levlaz 2y ago

ykonstant 2y ago
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]
- wirrbel 2y ago
  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
  - whatshisface 2y ago
    *Theoretical high-energy beyond-standard-model accelerator physics.
- ninetyninenine 2y ago
  > 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.
  - 2y ago
- nonameiguess 2y ago
  Not all that interested in debate, either, but it's hard to tell what you're really claiming here. It isn't the case with departments I'm aware of, certainly not where I went to school myself, that someone can graduate with a CS degree having taken nothing but theory courses. Tenured researchers can eventually specialize in that, but even PhD candidates have to demonstrate broad mastery of the entire core of CS across multiple sub-disciplines. Perhaps you're talking about the split between Electrical Engineering and Computer Science? That one isn't universal as some departments only offer EECS and not CS as a major, but when CS on its own is offered, "hardware" courses tend to be about microarchitecture, with practical work done using simulators. You're not required to know much of anything about electronics. But there is no program I'm aware of where a person can do nothing but math and get a CS degree. You have to write and test code.
- msravi 2y ago
  >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. This isn't really true, is it? There are mathematical models that predict but do not explain the real world. The most glaring of them is the transmission of EM waves without a medium, and the particle/wave duality of matter. In the former case, there was a concerted attempt to prove existence of the medium (luminiferous aether) that failed and ended up being discarded - we accept now that no medium is required, but we don't know the physical process of how that works.
  - westurner 2y ago
    We have lower error predictions but don't know why. Methods for explaining why include Counterfactual inference and/or now quantum Causal interference. All or some of quantum statistical mechanics, fluid dynamics, and quantum chaos intend to predict with lower error too
  - westurner 2y ago
    On the Cave and the Light, List of popular misconceptions and science > Science, technology, and mathematics : https://en.wikipedia.org/wiki/List_of_common_misconceptions https://en.wikipedia.org/wiki/List_of_common_misconceptions : > See also: Scientific misconceptions, Superseded theories in science, and List of topics characterized as pseudoscience Allegory of the cave > See also,: https://en.wikipedia.org/wiki/Allegory_of_the_cave https://en.wikipedia.org/wiki/Allegory_of_the_cave The only true statement: All models are wrong: https://en.wikipedia.org/wiki/All_models_are_wrong https://en.wikipedia.org/wiki/All_models_are_wrong Map–territory relation: https://en.wikipedia.org/wiki/Map%E2%80%93territory_relation https://en.wikipedia.org/wiki/Map%E2%80%93territory_relation : > A frequent coda to "all models are wrong" is that "all models are wrong (but some are useful)," which emphasizes the proper framing of recognizing map–territory differences—that is, how and why they are important, what to do about them, and how to live with them properly. The point is not that all maps are useless; rather, the point is simply to maintain critical thinking about the discrepancies: whether or not they are either negligible or significant in each context, how to reduce them (thus iterating a map, or any other model, to become a better version of itself), and so on.
youoy 2y ago
> 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-sounding-math-problem-was-a-century-in-the-making-20241014/ https://www.quantamagazine.org/big-advance-on-simple-soundin...
- bbor 2y ago
  Well put, but sadly I must disagree heartily. Mathematics is half of what drives/guides/underpins natural science, but it is not itself a natural science. As Kant teaches us in A Critique of Pure Reason, mathematics is the cultivation and extension of intuitive intellectual tools. This puts it in natural opposition to philosophy (which deals with conceptual intellectual tools) and natural science (which deals with the empirical nature of the Actual world). None of them would be very useful without the others, but that does not mean that we should abandon the distinctions, imo. That article is great, but I think the immediately preceding sentence is telling: Earlier that year, his father had died, and Pasten found himself turning to math for comfort. “I found mathematics really helpful for that,” he said. “Mathematics is not just about… To put it bluntly: I think that’s just cope. Again, I absolutely agree that mathematics can be useful for natural science, but we need to look no further than the multitude of mathematically-consistent models of the universe to see that it is not itself natural science.
  - youoy 2y ago
    Yes! I agree with you, mathematics is not a natural science. You can study the physical reality or the intellectual reality, mathematics would be closer to the intellectual reality. I guess this points back to the eternal debate about if mathematical objects are invented or discovered. If they are discovered, then that would mean that there is an underlying truth/semantics behind the mathematical formalisms. So in that case mathematics studies and interacts with reality. Take for example Calculus and Newton and Leibniz [0] who invented/discovered calculus independently. I will let you decide on what side of the debate you feel more comfortable :) [0] https://en.m.wikipedia.org/wiki/Leibniz%E2%80%93Newton_calculus_controversy https://en.m.wikipedia.org/wiki/Leibniz%E2%80%93Newton_calcu...
calf 2y ago
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 https://www.scottaaronson.com/papers/pnp.pdf
hrkucuk 2y ago
>“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).
- youoy 2y ago
  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.
  - tightbookkeeper 2y ago
    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.
- cubefox 2y ago
  My guess is that von Neumann worried that it develops in directions that people happen to find interesting, instead of in directions that are important by some objective external measure.
PeterStuer 2y ago
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".
- psychoslave 2y ago
  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.
  - PeterStuer 2y ago
    But how is that supported by TCS?
- pmontra 2y ago
  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.
  - PeterStuer 2y ago
    How about we start by introducing time, interactions with things exterior to the subsystem modeled?
  - GenericCanadian 2y ago
    Sounds a lot like what Wolfram is working on with categorizing cellular automota. Strikes me that a lot of his work is very biological in its search for axioms from experimentation
cjfd 2y ago
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.
- eru 2y ago
  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.)
  - cjfd 2y ago
    '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.
- globular-toast 2y ago
  The Turing machine is an artificial system constructed to be easy to reason about. The computer on my desk is most certainly not!
  - cjfd 2y ago
    Well, it depends. Have you ever considered writing a word processor in a Turing machine?
deleted 2y ago
[deleted]
peterkos 2y ago
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.
- karmakurtisaani 2y ago
  There's absolutely no hand waving in TCS. Everything is as rigorous as in any other subfield if math. But asymptotics are heavily used, true. That is because often the theoretically interesting properties appear only when the inputs are huge (I'm sure this happens in other areas as well).
n00b101 2y ago
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.
- youoy 2y ago
  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
- calf 2y ago
  Did Vardi write about this? I only found some other authors instead; is it possible you are referring to Yuri Manin instead? : From https://arxiv.org/pdf/1010.2067 https://arxiv.org/pdf/1010.2067 "Manin and Marcolli [20] derived similar results in a broader context and studied phase transitions in those systems. Manin [18, 19] also outlined an ambitious program to treat the infinite runtimes one finds in undecidable problems as singularities to be removed through the process of renormalization. In a manner reminiscent of hunting for the proper definition of the “one-element field” F_un, he collected ideas from many different places and considered how they all touch on this central theme. While he mentioned a runtime cutoff as being analogous to an energy cutoff, the renormalizations he presented are uncomputable. In this paper, we take the log of the runtime as being analogous to the energy; the randomness described by Chaitin and Tadaki then arises as the infinite-temperature limit."
sampo 2y ago
> 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.
- coliveira 2y ago
  In this case I believe it will take a whole generation. People will have to retire before we see the mainstream openly agree that it was a failed attempt.
- layer8 2y ago
  I recommend taking a listen to these podcast episodes to get an understanding of why string theory won’t be discarded anytime soon: https://www.preposterousuniverse.com/podcast/2018/10/15/episode-18-clifford-johnson-on-whats-so-great-about-superstring-theory/ https://www.preposterousuniverse.com/podcast/2018/10/15/epis... https://www.preposterousuniverse.com/podcast/2019/01/28/episode-31-brian-greene-on-the-multiverse-inflation-and-the-string-theory-landscape/ https://www.preposterousuniverse.com/podcast/2019/01/28/epis...
lincpa 2y ago
[dead]
epgui 2y ago
I’m just a biochemist/engineer who is passionate about other sciences, but IMHO his understanding of mathematics is what is counter-productive. It’s a bizarrely anti-intellectual take from someone who is clearly an intellectual.
aaron695 2y ago
[dead]
pron 2y ago
> NP-completeness theory, however, does not explain or predict the unreasonable effectiveness of SAT solvers. I don't think that's a fair characterisation. Clearly, the SAT subset that SAT solvers solve efficiently is in P, so in that sense complexity theory "explains" it and even "predicts" it: clearly, there are subsets of SAT in P; some simple ones, such as 2SAT, can be easily described. What complexity theory is yet to do is: 1. Either prove that the subset of SAT that can be solved efficiently covers all of SAT (in which case either P=NP or NP can be solved with such a low exponent that makes it tractable in practice) or identify and succinctly describe the subset of SAT that modern solvers solve efficiently, and it is in that sense that it doesn't yet "predict" it. But there are many open questions (including P vs NP) in complexity theory; that doesn't mean that the discipline is flawed. Many problems studied in complexity theory originate from practical questions, such as cryptography, and complexity theory does successfully and usefully explain and predict such real-world "phenomena". 2. Explain why that subset of SAT is prevalent in practice (making solvers "effective"). I'm not sure this is the job for complexity theory or any theoretical discipline for that matter (as opposed to empirical ones); after all theoretical computer science is meant to be theoretical. But there are mathematical disciplines (e.g. random graph theory) that do describe and even explain and predict mathematical structures that are more likely to arise in "nature". > U.S. TCS has a quite narrower scope than European TCS, which I find unfortunate. TCS is generally considered to have two primary subdisciplines: Theory of Computation (ToC, sometimes also referred to as "Theory A"), which is concerned with complexity and algorithms, and Theory of Programming (ToP, sometimes also referred to as "Theory B"), which is concerned with programming languages and type systems (and may be considered a sub-discipline of formal logic). Indeed, US ToC is more prominent in the US while ToP is more prominent in Europe, but I don't think some of the other CS sub-disciplines Moshe mentions (such as databases) are commonly considered theoretical computer science. I don't have a position on the utility of describing theoretical computer science as a branch of mathematics or not doing so, but the very name "theoretical computer science" acknowledges that there are other sub-disciplines in computer science that are empirical rather than theoretical (such as studying the mistakes programmers empirically make, or the common causes for cascading failures, or studying side-channel attacks etc. etc.). I don't think that those who consider TCS to be a branch of mathematics also consider all of CS to be a branch of mathematics or claim that theoretical computer science should aim to answer all interesting questions in computing, just as theoretical physics acknowledges the necessity of experimental physics and doesn't claim to cover everything physicists do. As in theoretical physics and mathematics, results in theoretical computer science do sometimes explain and predict things we observe in the real world and sometimes not yet. But in all these cases, the theoretical subdisciplines aren't wholly subservient to the empirical ones or vice-versa. As an example, the question of computability (decidability) isn't directly practical (as many decidable problems arent practically tractable), but the more practical question of tractability/complexity directly evolved from the study of computability.
poulpy123 2y ago
it's when I'm a computer scientist, theoretically
bbor 2y ago
I’m late to the party but I’ll drop the truth at the bottom: computer science in its own right is just modern philosophy of mind. It’s the specification of the conceptual limits of cognition. I love his “sociological sense”, and agree that at some level all these words are just words in language games that are defined with great diversity across the world’s academics, much less engineers and laypeople. But I also agree that there’s something worth defending in “computer science in its own right”, as I said above; that is, in turn, the core task of philosophy of science. Of course I would expect him to push back on this description of the field because philosophy has lost all its street cred, but that would only encourage me to redouble my efforts. If it’s not empirical study of actual results, and it’s not mathematical study of intuitively-based theorems, what else is left?
Peteragain 2y ago
I have often argued that computer scientists should be more interested in FPGAs and ASICs. Does the notion of Turing complete apply to a stack of LUTs? Look up tables are of course a nice mathematical generalisation. And how does that relate to prolog?
mirrorlake 2y ago
I quite like the sociological definition for several reasons. Rather than trying to pin down precise criteria, you simple can ask people "Are you a mathematician? Are you a theoretical computer scientist?" And once someone has gone through that filter, everything that follows is opinion and also a historical snapshot of what people felt the field contained at the time. It provides future theoreticians and students a way to orient themselves on a map which is only partially drawn. The definition of "theoretical physics" might have rapidly changed between 1900, 1920, 1940, and 1950--but certainly people who called themselves theoreticians remained mostly unchanged. Analyzing how everyone's definitions were changing gives a wealth of information about when and where breakthroughs were happening. 1919 and 1945 come to mind as such examples of when a theoretical field changed as a result of experiments [1][2]. Back to computing: Dijkstra told the story of attempting to put "Programmer" as his profession on his marriage certificate in 1957, and was rejected [3]. Clearly there are both pros and cons of using the sociological definition of a field. We all know programming existed before 1957, but the perception of it as a profession was so foreign that it wasn't allowed on an official document. It would've been impossible, apparently, where he lived to ponder about "What is programming?" if no one could BE a programmer. For that reason, we should probably be flexible and always be willing to discuss different definitions for every field so that we gain the benefits from multiple lines of reasoning. [1] https://en.wikipedia.org/wiki/Eddington_experiment https://en.wikipedia.org/wiki/Eddington_experiment [2] https://en.wikipedia.org/wiki/Trinity_(nuclear_test) https://en.wikipedia.org/wiki/Trinity_(nuclear_test) [3] https://amturing.acm.org/award_winners/dijkstra_1053701.cfm https://amturing.acm.org/award_winners/dijkstra_1053701.cfm
oglop 2y ago
I don’t know. It seems like a total mess to me and everyone deeply immersed in it a broken person. Horrible science. Horrible. Look how broken the society is when everyone gets a computer. Awful. Just awful. But can’t stop what’s coming, but I also don’t have to pretend CS is coherent or interesting or even a science (it’s not).
abdullahkhalids 2y ago
> 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. Incidentally, real-life computing depends quite a lot on the laws of the physics of the universe we live in. This has been known quite clearly since the theoretical discovery of quantum computing, with the resultant split of classical complexity theory and quantum complexity theory. Morever, physics also determines what sort of devices you can make and with what performance. The real-life speed of solving NP-complete problems depends on the absolute and relative performance of transistors, CPUs, memories etc. Hence, I submit that TCS has the same relationship to Physics as does Mechanical Engineering to Physics.
aabajian 2y ago
My master's degree in computer science technically says, "Theoretical computer science" as the specialization. I was a mathematics undergrad, and generally enjoy doing proofs, albeit I'm not the best at them. With that said, I regard TCS as the study of discretized computation at scale. Or, more colloquially, what is the fastest way to do X, N times? This could be sorting, searching, indexing, drawing, tracking, balancing, storing, accessing, saving, reading, writing, whatever. The distinguishing characteristic is complexity analysis in time and space. As a counterexample, I think cryptographic methods such as AES and RSA are much more pure math / number theory than TCS.
necovek 2y ago
I am a bit confused. The argument seems to be that 1. a theoretical computer scientist is not a general mathematician and wouldn't be hired to a tenured math position ("sociological argument") and 2. treating it as a branch of math is "harmful" to theoretical computer science. There are hints about what OP believes TCS is which isn't math, but I wonder why not make that an explicit argument — that would make it much easier to reason about and argue either for or against. Without that, neither 1 nor 2 make a convincing case for anything: 1. a Linear Algebra expert might not get a position in a Statistics department either, and 2. it'd be useful to show some "harm" before you claim anything being "harmful". CS is also lucrative enough that it pays to have a dedicated faculty just for CS too (as in, it attracts students, contracts with external parties for a university, etc).
- m463 2y ago
  X = X + 1 this makes it obvious why theoretical math and theoretical computer science cannot co-exist.
  - lavp 2y ago
    What you described is syntax differences. `=` is assignment, not equivalence.
fauria 2y ago
Link to the excellent book "Mathematics and Computation" by Avi Wigderson mentioned in the article (PDF): https://www.math.ias.edu/files/Book-online-Aug0619.pdf https://www.math.ias.edu/files/Book-online-Aug0619.pdf Source: https://www.math.ias.edu/avi/book https://www.math.ias.edu/avi/book
black_13 2y ago
[dead]
sebastialonso 2y ago
Interesting topic! Completely disagree with his take though. > The centrality of computing stems from the fact that it is a technology that has been changing the world for the past 80 years, ever since the British used early computing to change the tide of war in World War II. I take issue with the idea hinted at here. Just like Algebra and other branches of mathematics were invented to deal with daily down-to-earth issues like accounting or farming, you'd be hard pressed to find a consensus that mathematics "aims to explain the real world". The historical origin is very clear, but the train left the "real world" station pretty fast, "unreasonable effectiveness" notwithstanding. Am I to understand that because Enigma was broken using a physical machine, the field is bound to study physical reality? To me this feels as uncomfortable as to refer to astronomy as "telescope studies". > I believe that thinking of TCS as a branch of mathematics is harmful to the discipline. [...] > 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 Yeah, if you hired me to design harmful approaches, not in a year I would have come up with something as harmful as this.
nmaleki 2y ago
This: https://recursion.is https://recursion.is

167 points by levlaz 2y ago

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]

wirrbel 2y ago
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
- whatshisface 2y ago
  *Theoretical high-energy beyond-standard-model accelerator physics.
ninetyninenine 2y ago
> 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.
- 2y ago
nonameiguess 2y ago
Not all that interested in debate, either, but it's hard to tell what you're really claiming here. It isn't the case with departments I'm aware of, certainly not where I went to school myself, that someone can graduate with a CS degree having taken nothing but theory courses. Tenured researchers can eventually specialize in that, but even PhD candidates have to demonstrate broad mastery of the entire core of CS across multiple sub-disciplines. Perhaps you're talking about the split between Electrical Engineering and Computer Science? That one isn't universal as some departments only offer EECS and not CS as a major, but when CS on its own is offered, "hardware" courses tend to be about microarchitecture, with practical work done using simulators. You're not required to know much of anything about electronics. But there is no program I'm aware of where a person can do nothing but math and get a CS degree. You have to write and test code.
msravi 2y ago
>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. This isn't really true, is it? There are mathematical models that predict but do not explain the real world. The most glaring of them is the transmission of EM waves without a medium, and the particle/wave duality of matter. In the former case, there was a concerted attempt to prove existence of the medium (luminiferous aether) that failed and ended up being discarded - we accept now that no medium is required, but we don't know the physical process of how that works.
- westurner 2y ago
  We have lower error predictions but don't know why. Methods for explaining why include Counterfactual inference and/or now quantum Causal interference. All or some of quantum statistical mechanics, fluid dynamics, and quantum chaos intend to predict with lower error too
- westurner 2y ago
  On the Cave and the Light, List of popular misconceptions and science > Science, technology, and mathematics : https://en.wikipedia.org/wiki/List_of_common_misconceptions https://en.wikipedia.org/wiki/List_of_common_misconceptions : > See also: Scientific misconceptions, Superseded theories in science, and List of topics characterized as pseudoscience Allegory of the cave > See also,: https://en.wikipedia.org/wiki/Allegory_of_the_cave https://en.wikipedia.org/wiki/Allegory_of_the_cave The only true statement: All models are wrong: https://en.wikipedia.org/wiki/All_models_are_wrong https://en.wikipedia.org/wiki/All_models_are_wrong Map–territory relation: https://en.wikipedia.org/wiki/Map%E2%80%93territory_relation https://en.wikipedia.org/wiki/Map%E2%80%93territory_relation : > A frequent coda to "all models are wrong" is that "all models are wrong (but some are useful)," which emphasizes the proper framing of recognizing map–territory differences—that is, how and why they are important, what to do about them, and how to live with them properly. The point is not that all maps are useless; rather, the point is simply to maintain critical thinking about the discrepancies: whether or not they are either negligible or significant in each context, how to reduce them (thus iterating a map, or any other model, to become a better version of itself), and so on.

youoy 2y ago

> 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-sounding-math-problem-was-a-century-in-the-making-20241014/ https://www.quantamagazine.org/big-advance-on-simple-soundin...

bbor 2y ago
Well put, but sadly I must disagree heartily. Mathematics is half of what drives/guides/underpins natural science, but it is not itself a natural science. As Kant teaches us in A Critique of Pure Reason, mathematics is the cultivation and extension of intuitive intellectual tools. This puts it in natural opposition to philosophy (which deals with conceptual intellectual tools) and natural science (which deals with the empirical nature of the Actual world). None of them would be very useful without the others, but that does not mean that we should abandon the distinctions, imo. That article is great, but I think the immediately preceding sentence is telling: Earlier that year, his father had died, and Pasten found himself turning to math for comfort. “I found mathematics really helpful for that,” he said. “Mathematics is not just about… To put it bluntly: I think that’s just cope. Again, I absolutely agree that mathematics can be useful for natural science, but we need to look no further than the multitude of mathematically-consistent models of the universe to see that it is not itself natural science.
- youoy 2y ago
  Yes! I agree with you, mathematics is not a natural science. You can study the physical reality or the intellectual reality, mathematics would be closer to the intellectual reality. I guess this points back to the eternal debate about if mathematical objects are invented or discovered. If they are discovered, then that would mean that there is an underlying truth/semantics behind the mathematical formalisms. So in that case mathematics studies and interacts with reality. Take for example Calculus and Newton and Leibniz [0] who invented/discovered calculus independently. I will let you decide on what side of the debate you feel more comfortable :) [0] https://en.m.wikipedia.org/wiki/Leibniz%E2%80%93Newton_calculus_controversy https://en.m.wikipedia.org/wiki/Leibniz%E2%80%93Newton_calcu...

calf 2y ago

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 https://www.scottaaronson.com/papers/pnp.pdf

hrkucuk 2y ago

>“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).

youoy 2y ago
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.
- tightbookkeeper 2y ago
  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.
cubefox 2y ago
My guess is that von Neumann worried that it develops in directions that people happen to find interesting, instead of in directions that are important by some objective external measure.

PeterStuer 2y ago

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

psychoslave 2y ago
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.
- PeterStuer 2y ago
  But how is that supported by TCS?
pmontra 2y ago
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.
- PeterStuer 2y ago
  How about we start by introducing time, interactions with things exterior to the subsystem modeled?
- GenericCanadian 2y ago
  Sounds a lot like what Wolfram is working on with categorizing cellular automota. Strikes me that a lot of his work is very biological in its search for axioms from experimentation

cjfd 2y ago

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.

eru 2y ago
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.)
- cjfd 2y ago
  '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.
globular-toast 2y ago
The Turing machine is an artificial system constructed to be easy to reason about. The computer on my desk is most certainly not!
- cjfd 2y ago
  Well, it depends. Have you ever considered writing a word processor in a Turing machine?

deleted 2y ago

[deleted]

peterkos 2y ago

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.

karmakurtisaani 2y ago
There's absolutely no hand waving in TCS. Everything is as rigorous as in any other subfield if math. But asymptotics are heavily used, true. That is because often the theoretically interesting properties appear only when the inputs are huge (I'm sure this happens in other areas as well).

n00b101 2y ago

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.

youoy 2y ago
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
calf 2y ago
Did Vardi write about this? I only found some other authors instead; is it possible you are referring to Yuri Manin instead? : From https://arxiv.org/pdf/1010.2067 https://arxiv.org/pdf/1010.2067 "Manin and Marcolli [20] derived similar results in a broader context and studied phase transitions in those systems. Manin [18, 19] also outlined an ambitious program to treat the infinite runtimes one finds in undecidable problems as singularities to be removed through the process of renormalization. In a manner reminiscent of hunting for the proper definition of the “one-element field” F_un, he collected ideas from many different places and considered how they all touch on this central theme. While he mentioned a runtime cutoff as being analogous to an energy cutoff, the renormalizations he presented are uncomputable. In this paper, we take the log of the runtime as being analogous to the energy; the randomness described by Chaitin and Tadaki then arises as the infinite-temperature limit."

sampo 2y ago

coliveira 2y ago
In this case I believe it will take a whole generation. People will have to retire before we see the mainstream openly agree that it was a failed attempt.
layer8 2y ago
I recommend taking a listen to these podcast episodes to get an understanding of why string theory won’t be discarded anytime soon: https://www.preposterousuniverse.com/podcast/2018/10/15/episode-18-clifford-johnson-on-whats-so-great-about-superstring-theory/ https://www.preposterousuniverse.com/podcast/2018/10/15/epis... https://www.preposterousuniverse.com/podcast/2019/01/28/episode-31-brian-greene-on-the-multiverse-inflation-and-the-string-theory-landscape/ https://www.preposterousuniverse.com/podcast/2019/01/28/epis...

lincpa 2y ago

[dead]

epgui 2y ago

I’m just a biochemist/engineer who is passionate about other sciences, but IMHO his understanding of mathematics is what is counter-productive. It’s a bizarrely anti-intellectual take from someone who is clearly an intellectual.

aaron695 2y ago

[dead]

pron 2y ago

> NP-completeness theory, however, does not explain or predict the unreasonable effectiveness of SAT solvers. I don't think that's a fair characterisation. Clearly, the SAT subset that SAT solvers solve efficiently is in P, so in that sense complexity theory "explains" it and even "predicts" it: clearly, there are subsets of SAT in P; some simple ones, such as 2SAT, can be easily described. What complexity theory is yet to do is: 1. Either prove that the subset of SAT that can be solved efficiently covers all of SAT (in which case either P=NP or NP can be solved with such a low exponent that makes it tractable in practice) or identify and succinctly describe the subset of SAT that modern solvers solve efficiently, and it is in that sense that it doesn't yet "predict" it. But there are many open questions (including P vs NP) in complexity theory; that doesn't mean that the discipline is flawed. Many problems studied in complexity theory originate from practical questions, such as cryptography, and complexity theory does successfully and usefully explain and predict such real-world "phenomena". 2. Explain why that subset of SAT is prevalent in practice (making solvers "effective"). I'm not sure this is the job for complexity theory or any theoretical discipline for that matter (as opposed to empirical ones); after all theoretical computer science is meant to be theoretical. But there are mathematical disciplines (e.g. random graph theory) that do describe and even explain and predict mathematical structures that are more likely to arise in "nature". > U.S. TCS has a quite narrower scope than European TCS, which I find unfortunate. TCS is generally considered to have two primary subdisciplines: Theory of Computation (ToC, sometimes also referred to as "Theory A"), which is concerned with complexity and algorithms, and Theory of Programming (ToP, sometimes also referred to as "Theory B"), which is concerned with programming languages and type systems (and may be considered a sub-discipline of formal logic). Indeed, US ToC is more prominent in the US while ToP is more prominent in Europe, but I don't think some of the other CS sub-disciplines Moshe mentions (such as databases) are commonly considered theoretical computer science. I don't have a position on the utility of describing theoretical computer science as a branch of mathematics or not doing so, but the very name "theoretical computer science" acknowledges that there are other sub-disciplines in computer science that are empirical rather than theoretical (such as studying the mistakes programmers empirically make, or the common causes for cascading failures, or studying side-channel attacks etc. etc.). I don't think that those who consider TCS to be a branch of mathematics also consider all of CS to be a branch of mathematics or claim that theoretical computer science should aim to answer all interesting questions in computing, just as theoretical physics acknowledges the necessity of experimental physics and doesn't claim to cover everything physicists do. As in theoretical physics and mathematics, results in theoretical computer science do sometimes explain and predict things we observe in the real world and sometimes not yet. But in all these cases, the theoretical subdisciplines aren't wholly subservient to the empirical ones or vice-versa. As an example, the question of computability (decidability) isn't directly practical (as many decidable problems arent practically tractable), but the more practical question of tractability/complexity directly evolved from the study of computability.

poulpy123 2y ago

it's when I'm a computer scientist, theoretically

bbor 2y ago

I’m late to the party but I’ll drop the truth at the bottom: computer science in its own right is just modern philosophy of mind. It’s the specification of the conceptual limits of cognition. I love his “sociological sense”, and agree that at some level all these words are just words in language games that are defined with great diversity across the world’s academics, much less engineers and laypeople. But I also agree that there’s something worth defending in “computer science in its own right”, as I said above; that is, in turn, the core task of philosophy of science. Of course I would expect him to push back on this description of the field because philosophy has lost all its street cred, but that would only encourage me to redouble my efforts. If it’s not empirical study of actual results, and it’s not mathematical study of intuitively-based theorems, what else is left?

Peteragain 2y ago

I have often argued that computer scientists should be more interested in FPGAs and ASICs. Does the notion of Turing complete apply to a stack of LUTs? Look up tables are of course a nice mathematical generalisation. And how does that relate to prolog?

mirrorlake 2y ago

I quite like the sociological definition for several reasons. Rather than trying to pin down precise criteria, you simple can ask people "Are you a mathematician? Are you a theoretical computer scientist?" And once someone has gone through that filter, everything that follows is opinion and also a historical snapshot of what people felt the field contained at the time. It provides future theoreticians and students a way to orient themselves on a map which is only partially drawn. The definition of "theoretical physics" might have rapidly changed between 1900, 1920, 1940, and 1950--but certainly people who called themselves theoreticians remained mostly unchanged. Analyzing how everyone's definitions were changing gives a wealth of information about when and where breakthroughs were happening. 1919 and 1945 come to mind as such examples of when a theoretical field changed as a result of experiments [1][2]. Back to computing: Dijkstra told the story of attempting to put "Programmer" as his profession on his marriage certificate in 1957, and was rejected [3]. Clearly there are both pros and cons of using the sociological definition of a field. We all know programming existed before 1957, but the perception of it as a profession was so foreign that it wasn't allowed on an official document. It would've been impossible, apparently, where he lived to ponder about "What is programming?" if no one could BE a programmer. For that reason, we should probably be flexible and always be willing to discuss different definitions for every field so that we gain the benefits from multiple lines of reasoning. [1] https://en.wikipedia.org/wiki/Eddington_experiment https://en.wikipedia.org/wiki/Eddington_experiment [2] https://en.wikipedia.org/wiki/Trinity_(nuclear_test) https://en.wikipedia.org/wiki/Trinity_(nuclear_test) [3] https://amturing.acm.org/award_winners/dijkstra_1053701.cfm https://amturing.acm.org/award_winners/dijkstra_1053701.cfm

oglop 2y ago

I don’t know. It seems like a total mess to me and everyone deeply immersed in it a broken person. Horrible science. Horrible. Look how broken the society is when everyone gets a computer. Awful. Just awful. But can’t stop what’s coming, but I also don’t have to pretend CS is coherent or interesting or even a science (it’s not).

abdullahkhalids 2y ago

> 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. Incidentally, real-life computing depends quite a lot on the laws of the physics of the universe we live in. This has been known quite clearly since the theoretical discovery of quantum computing, with the resultant split of classical complexity theory and quantum complexity theory. Morever, physics also determines what sort of devices you can make and with what performance. The real-life speed of solving NP-complete problems depends on the absolute and relative performance of transistors, CPUs, memories etc. Hence, I submit that TCS has the same relationship to Physics as does Mechanical Engineering to Physics.

aabajian 2y ago

My master's degree in computer science technically says, "Theoretical computer science" as the specialization. I was a mathematics undergrad, and generally enjoy doing proofs, albeit I'm not the best at them. With that said, I regard TCS as the study of discretized computation at scale. Or, more colloquially, what is the fastest way to do X, N times? This could be sorting, searching, indexing, drawing, tracking, balancing, storing, accessing, saving, reading, writing, whatever. The distinguishing characteristic is complexity analysis in time and space. As a counterexample, I think cryptographic methods such as AES and RSA are much more pure math / number theory than TCS.

necovek 2y ago

I am a bit confused. The argument seems to be that 1. a theoretical computer scientist is not a general mathematician and wouldn't be hired to a tenured math position ("sociological argument") and 2. treating it as a branch of math is "harmful" to theoretical computer science. There are hints about what OP believes TCS is which isn't math, but I wonder why not make that an explicit argument — that would make it much easier to reason about and argue either for or against. Without that, neither 1 nor 2 make a convincing case for anything: 1. a Linear Algebra expert might not get a position in a Statistics department either, and 2. it'd be useful to show some "harm" before you claim anything being "harmful". CS is also lucrative enough that it pays to have a dedicated faculty just for CS too (as in, it attracts students, contracts with external parties for a university, etc).

m463 2y ago
X = X + 1 this makes it obvious why theoretical math and theoretical computer science cannot co-exist.
- lavp 2y ago
  What you described is syntax differences. `=` is assignment, not equivalence.

fauria 2y ago

Link to the excellent book "Mathematics and Computation" by Avi Wigderson mentioned in the article (PDF): https://www.math.ias.edu/files/Book-online-Aug0619.pdf https://www.math.ias.edu/files/Book-online-Aug0619.pdf Source: https://www.math.ias.edu/avi/book https://www.math.ias.edu/avi/book

black_13 2y ago

[dead]

sebastialonso 2y ago

Interesting topic! Completely disagree with his take though. > The centrality of computing stems from the fact that it is a technology that has been changing the world for the past 80 years, ever since the British used early computing to change the tide of war in World War II. I take issue with the idea hinted at here. Just like Algebra and other branches of mathematics were invented to deal with daily down-to-earth issues like accounting or farming, you'd be hard pressed to find a consensus that mathematics "aims to explain the real world". The historical origin is very clear, but the train left the "real world" station pretty fast, "unreasonable effectiveness" notwithstanding. Am I to understand that because Enigma was broken using a physical machine, the field is bound to study physical reality? To me this feels as uncomfortable as to refer to astronomy as "telescope studies". > I believe that thinking of TCS as a branch of mathematics is harmful to the discipline. [...] > 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 Yeah, if you hired me to design harmful approaches, not in a year I would have come up with something as harmful as this.

nmaleki 2y ago

This: https://recursion.is https://recursion.is