[HN Gopher] What is theoretical computer science?
___________________________________________________________________
What is theoretical computer science?
Author : levlaz
Score : 123 points
Date : 2024-10-18 06:04 UTC (16 hours ago)
(HTM) web link (cacm.acm.org)
(TXT) w3m dump (cacm.acm.org)
| ykonstant wrote:
| 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 wrote:
| 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 wrote:
| *Theoretical high-energy beyond-standard-model accelerator
| physics.
| ninetyninenine wrote:
| > 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.
| moring wrote:
| > 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.
| RandomThoughts3 wrote:
| I think both are wrong.
|
| Science has a word encompasses a broad variety of
| definitions and practices. The philosophical question of
| the relationship of empiricism to truth (because
| fundamentally the question has more to do with the
| relationship between observations and deductions than
| science in itself) is a complex one and overall of little
| interest to actual practitioners of science. It can't
| easily be subsumed in broad aphorisms.
|
| I would hazard that most modern sciences - and physics
| especially - are nowadays mostly concerned about building
| models and the resulting predictions. The question then
| often becomes: does the tool I have built allow me to
| correctly predict how observations will unfold? The answer
| to which is often more shades of grey than simply yes or
| no.
| epgui wrote:
| Science (as in the "natural sciences", ie.: everything that
| is not philosophy or mathematics) is not about "proving"
| anything at all.
|
| Science is about measuring, quantifying and qualifying
| uncertainty.
| ninetyninenine wrote:
| I answer it here:
|
| https://news.ycombinator.com/item?id=41851265
|
| If you want to learn more look up Karl popper. It's his
| philosophy.
|
| In response to the other sibling replies I'm basically
| talking about science as in the scientific method. What are
| the limits of the scientific method in terms of determining
| truth?
|
| One thing that isn't addressed is fundamentally limited
| accuracy and precision of observational instruments. This
| actually makes things not falsifiable as well but I don't
| talk about this because it complicates everything.
| greiskul wrote:
| Maybe you think you saw a black swan around the orbit of
| Jupiter with your new fancy telescope, but later you figure
| out that the telescope was falty and the swan you saw was
| actually white.
|
| Because science depends on the external world, and there
| might always be hidden variables that we are not
| considering, it can only give us extremely high confidence
| after we make repeated observations using different
| methods, but it cannot give us the absolute confidence that
| Math can give us.
|
| Also, this example of faulty telescopes is actually really
| close to what actually happened in the history of
| astronomy. Stars were thought to have a visible radius that
| made them appear to be much larger than the Sun, which was
| considered evidence that the Sun was not a regular star.
| ninetyninenine wrote:
| > it can only give us extremely high confidence
|
| Here's an interesting thing. Even high confidence can't
| be verified.
|
| Let's say you examined 10 million swans and you think you
| observed all possible swans. But there's no way you can
| know whether or not the actual population is 10 billion
| trillion swans or a google swans.
|
| If you observed 10 million swans and they are all white
| but those swans could only represent 1/99999999999999 of
| all possible swans. Then that means your observation is
| low confidence and there's no way whether we can verify
| what fraction of the population our sample size
| represents.
|
| So actually high confidence is just an assumption. At a
| very technical level the confidence that science brings
| to the table is very very weak. We are making tons of
| assumptions and jumping to conclusions all the time.
| Koshkin wrote:
| > _So actually high confidence is just an assumption._
|
| This one is actually a funny statement. Not all
| assumptions are born equal :)
| jacobsimon wrote:
| I think you're missing the broader point, which is that there
| is a lot to computer science outside of the purely
| mathematical formalism.
|
| For example, distributed systems and networking are more like
| a physical science because they seek to make generalized
| learnings and theorems about real world systems.
|
| The author's last point around complexity theory also
| resonates because it demonstrates the value of designing
| experiments with real-world conditions like computing
| hardware speed and input sizes.
| User23 wrote:
| Distributed systems are famously hard to get right and
| mathematical formalism is pretty much the only way to do so
| at scale. Amazon found that out with S3[1]. TLA+ exists for
| very good reason!
|
| That's not to discount the reality that mapping the model
| to reality is hard work that needs to be done.
|
| [1] https://lamport.azurewebsites.net/tla/formal-methods-
| amazon....
| ninetyninenine wrote:
| The topic is about theoretical computer science which I
| would say is a math.
|
| The authors last point is basically like what applied math
| is to math. It's applied computer science.
| auggierose wrote:
| It is either "a kind of math", or "math", but not "a
| math".
| ninetyninenine wrote:
| Sounds ok to me in casual conversation. I use it like
| fruit. Orange is a fruit. Orange is also a kind of fruit.
| Orange is fruit doesn't sound right though.
|
| Empathetically speaking I'm sure it's quite jarring for
| you when you read it.
| tzs wrote:
| > 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.
|
| An amusing thing about a hypothesis like "all swans are
| white" is that if you do want to go around making
| observations to support it you don't actually need to observe
| any swans.
|
| "All swans are white" is logically equivalent to "All non-
| white things are not swans". Thus you can gather
| observational evidence for the hypothesis by finding non-
| white things and checking if they are swans.
|
| My monitor is not white, and I see it is not a swan. I've
| just made an observation in support of "all swans are white".
| I can make hundreds of such observations without even leaving
| my house.
|
| I feel sorry for all those other swan color researchers who
| had to trudge around slimy rivers and mucky wetlands checking
| the colors of swans.
|
| I think I first saw this in a Martin Gardner book. It is
| amusing, but actually there has been quite a bit of serious
| work among logicians and philosophers over this [1] since the
| logic seems correct but intuitively it seems you shouldn't be
| able to research swan color by looking around at the
| furniture in your house.
|
| [1] https://en.wikipedia.org/wiki/Raven_paradox
| ninetyninenine wrote:
| This suffers from the same issue. Just like how you can't
| observe all swans, you can't observe all non white things.
|
| The negation and the original statement can't be proven.
| They can only be falsified.
|
| The reason why you can't prove things in science is because
| reality is unbounded so at any point in time in the future
| you may observe something that contradicts the hypothesis.
| bee_rider wrote:
| Agreed on the scientific method point, this is a really
| fundamental issue and it is shocking to me when people talk
| about science as if things are being proven in the same
| fashion as math. Maybe we need to sneak a "philosophy of
| science" into the k-12 system.
|
| But I think there is also an etymological issue or something
| as well, which is causing additional confusion. Scientific
| theories aren't proven of course, but they are proofed, in
| the same manner as when you pick up a breastplate from the
| blacksmith and note that it has a dent in it from where he
| shot it once. That's the proof mark, the armor was tested by
| giving it a reasonably challenging test that is appropriate
| to the task it is intended for. Does this _prove_ the armor
| is indestructible? No, of course not, as a physical device
| the armor has some finite limitations which could be overcome
| with enough gunpowder. But it is still reassuring.
|
| Therefore I propose we clearly delineate between the two, by
| always spelling the logic thing with a _ve_ and the "well, I
| tested it pretty hard and it didn't break" thing with an _f_.
|
| Newtonian physics was mostly mechanical engineering proof. It
| turns out electrical engineering, the study of fields and
| waves, that was a higher caliber. The standard model seems to
| be EE proof. But physicists are always constructing more
| energetic experiments.
| ninetyninenine wrote:
| Well proof and prove is the same word in adjective and noun
| form. If we change the definitions we lose the usage of
| nouns and verb. - I proof the armor is
| solid - That's a mathematical prove.
|
| Doesn't sound right either imo.
| bee_rider wrote:
| It could just be that they are unfamiliar though, right?
|
| "The armor has been proofed" doesn't look so bad. "The
| armor has been proven" actually looks a tiny bit more
| awkward to me because it brings in too much of the math
| meaning.
|
| Prove as a noun, though, I agree it is a little awkward.
|
| But this is a request to change the language (where are
| those filed?) so I guess we will get used to it if it
| goes through.
| BoiledCabbage wrote:
| > No this guy doesn't get it. He doesn't understand what
| science is.
|
| > In science nothing can be proven.
|
| Who are you referring to? Nobody has mentioned anything about
| proven. Your entire comment is focused on arguing against
| science being proofs, but nobody has said science is proofs.
|
| OP said that scientific theories should "explain and predict"
| which they should. Those that don't should be discarded
| eventually (which they should). Why are your discussing
| mathematical proofs of science when nobody brought it up nor
| proposed that?
| ninetyninenine wrote:
| Im demarcating what science is and what math is.
| - In science nothing can be proven. - In math
| things can be proven.
|
| From those two points above we know this:
| - computer science is not a science because you can prove
| things - computer science is a kind of math because
| you can prove things
|
| This goes fully against the ops main point that computer
| science isn't math when it is. There's a big nomenclature
| issue that confuses everyone, him and you, and it just
| throws everyone off in terms of clear categorical thinking.
| Namely, Computer science is not actually a science.
|
| You guys don't understand what math is and you don't
| understand what science is and thus you guys are
| classifying incorrectly that computer science isn't a math
| and they are making a completely invalid comparison with
| physics which is actually a science.
| BoiledCabbage wrote:
| Ah, I see what you're misunderstanding. You're not
| thinking about the problem in the correct light.
|
| If you start with the premise that computer science is
| math, of course you'll reach the conclusion that computer
| science is math. And that's why you're so surprised that
| anyone else can reach any other conclusion. But the issue
| is in your premise - that's what you need to re-examine.
|
| The math portions of computer science are math - and the
| non math portions are not. Your argument is equivalent to
| saying that Europe is defined by the counties in that
| continent using GMT - and concluding "Of course Italy
| isn't in Europe!".
|
| Parts of Computer Science (the theoretical parts) sit in
| formal science just like logic and math do. But parts of
| CS like applied CS don't. All of the hardware design and
| software falls into applied CS and eventually slides into
| pure engineering.
|
| But CS also is more amorphous than many other
| disciplines. Parts of it almost touch up against
| behavioral science with its subfield of linguistics, and
| syntax and semantics of language. And a failure of CS
| over the past 50 years has been the utter lack of
| progress in empirical data around human modeling of
| computation. We still don't have any empirical framework
| for evaluating what languages or modeling approaches are
| more efficient than others, or even what makes a more
| efficient programing language. As a result that is stuck
| in alchemy and cargo culting.
|
| Models of computation and information theory begin to
| intersect with the natural sciences n the realm of
| physics. Physicists begin to push up against what is
| computable by nature in a given region of space. And
| Quantum computation begins to redefine what the physical
| bounds are on computation.
|
| Don't begin by looking at what math is - if you do then
| the only thing possible to conclude is that it's math .
| An informal definition you could begin with might be "The
| theory and application of tools (ie formal cs) and models
| (ie applied cs) that predict and explain behavior related
| to Computation"
|
| How do you model the real world via computation? What are
| the limits of computation? How do you implement
| computation?
|
| Computer Science is the study of all aspects of
| computation.
| ninetyninenine wrote:
| False, it is you who misunderstands and your terminology
| is incorrect.
|
| The term is "theoretical computer science." Not just
| "computer science"
|
| https://www.wikiwand.com/en/articles/Computer_science
|
| https://www.wikiwand.com/en/articles/Theoretical_computer
| _sc...
|
| The OP is making a claim on "theoretical computer
| science" NOT "computer science". Hence the title "What is
| theoretical computer science".
|
| If you look at the wiki entry you will see that
| "Theoretical computer science" is highly mathematical and
| different from "computer science".
|
| Honestly even I mis-used the term and this leads to tons
| of confusion. The naming of everything really changes the
| way people think and mixes everyone up. It's entirely a
| linguistic problem.
| 3np wrote:
| I mean...
|
| Consider this school of thought: My school burned down
| last week. The one where I went to elementary school.
|
| A strawberry is not botanically a berry. A peanut is not
| a nut. A tomato is either a fruit or a vegetable. Nobody
| thinks this is a problem.
|
| This is just language. Perhaps it's not actually a big
| deal that "Theoretical Computer Science" does not cleanly
| fall into your usual "Science" label?
| ninetyninenine wrote:
| >This is just language. Perhaps it's not actually a big
| deal that "Theoretical Computer Science" does not cleanly
| fall into your usual "Science" label?
|
| What are you talking about? You're regurgitating points I
| already made as if I never made those points...
|
| I literally said Computer science is NOT a science.
|
| I said several times, it's a linguistic/nomenclature
| issue.
|
| I don't think you're reading my responses. Are you
| trolling? If not please read over my responses more
| carefully.
| 3np wrote:
| So, we are acknowledging that there exist parallel non-
| overlaping equally valid notions and definitions of
| science.
|
| Menawhile, you seem pretty hung up on the "In Science,
| nothing can be proven" part of a whole long argument as
| to why CS shouldn't be referred to as a science. Perhaps
| that distinction is not useful or relevant in context?
| ninetyninenine wrote:
| >So, we are acknowledging that there exist parallel non-
| overlaping equally valid notions and definitions of
| science.
|
| False. I said I acknowledge linguistic issues that can
| cause confusion. There is overlap but there is NO
| contradiction. There isn't a case where there are two
| conflicting definitions for a single term.
|
| >Menawhile, you seem pretty hung up on the "In Science,
| nothing can be proven" part of a whole long argument as
| to why CS shouldn't be referred to as a science. Perhaps
| that distinction is not useful or relevant in context?
|
| Meanwhile you seem hung up on me setting up clear and
| categorical distinctions as not useful or relevant.
|
| Let me make it clear why your hang up doesn't make sense.
| The entire topic of this thread is an argument for "why
| CS isn't math." I am staying on topic and saying that CS
| IS a MATH and NOT a SCIENCE. Thus because I am on topic
| the distinction is ON context and HIGHLY relevant. You
| can disagree and state your points but saying my point
| isn't relevant is false.
|
| It's not a valid argument. I literally stated the premise
| is false and stated the reason why, and you stated the
| reason is off topic as if I changed the topic .
| Koshkin wrote:
| > _I literally said Computer science is NOT a science._
|
| But the point was that this entirely depends on one's
| definition of what the word "science" means - and that
| depends on the context and the language. I can say, for
| example, that math is science - simply equating "science"
| with "knowledge" and "research".
| ninetyninenine wrote:
| >But the point was that this entirely depends on one's
| definition of what the word "science" means - and that
| depends on the context and the language. I can say, for
| example, that math is science - simply equating "science"
| with "knowledge" and "research".
|
| And I stated this in this thread several times. I defined
| what science is and I literally said, Computer Science
| isn't ACTUALLY a Science. It's incorrect terminology due
| to historical reasons. It's similar to greenland.
| Greenland isn't actually Green.
|
| If you followed carefully what I wrote in this thread I
| defined what definition of science I'm using very very
| clearly and I ALSO stated why for the context of defining
| what "Theoretical Computer Science" using this definition
| has the most utility for the task at hand.
|
| Look, not just you Koshkin, but everyone. This isn't even
| a thing that's really up for debate. Look at the
| wikipedia page for "theoretical computer science". The
| FIRST intro literally says it's the mathematical
| foundations for computation.
|
| https://www.wikiwand.com/en/articles/Theoretical_computer
| _sc...
| Koshkin wrote:
| > _- In math things can be proven._
|
| Some things can, some cannot (be either proven or shown
| to be false).
| ninetyninenine wrote:
| Right so I never said anything to the contrary. In fact,
| ironically, it's been proven that in Math there are
| statements that are true, but can never be proven to be
| true. See Godel.
| lisper wrote:
| > If I say all swans are white as my hypothesis
|
| That fails as a scientific hypothesis on purely structural
| grounds, before you have made any observations. Scientific
| hypotheses have to _explain_ something. It 's not enough to
| say that all swans are white, you have to say _why_. "All
| swans are white" is an observation, not a (scientific)
| hypothesis.
|
| An example of a legitimate scientific hypothesis is that all
| swans are white _because_ being white provides swans with
| some benefit in terms of reproductive fitness (and then you
| have to go on to say what that benefit is). You can then go
| on to _predict_ that there _might_ be non-white swans, but
| that these are expected to be rare because evolutionary
| pressure would drive non-whiteness out of the gene pool. Or
| something like that. But "all swans are white" by itself is
| a non-starter as a scientific hypothesis.
| ninetyninenine wrote:
| I'm talking at a very technical level ignoring all the
| cultural stuff around the scientific method like "peer
| review" or explaining "why"
|
| Basically a hypothesis is a statement that can be true or
| false. That's it.
|
| The reason I refer to science in this very technical way is
| because the we are tackling the problem of classification.
| We are asking the question what is computer science? So to
| answer the question we need to use very technical
| definitions where the boundaries of categorization are
| extremely clear.
|
| Again, at a very technical level a hypothesis is simply a
| statement that is true or false.
| abeppu wrote:
| I think it's a mistake to frame "why" as "cultural stuff
| around the scientific method" but not actually part of
| science.
|
| > Basically a hypothesis is a statement that can be true
| or false. That's it.
|
| No, a statement which can be true or false is just a
| proposition. The reason that we care about "why" is that
| a hypothesis has bearing on _many_ falsifiable
| propositions. It 's the difference between "the specific
| rock I dropped accelerated at 9.8 m/s^2" and Newton's law
| of universal gravitation.
| ninetyninenine wrote:
| I explain here:
|
| https://news.ycombinator.com/item?id=41882469
| lisper wrote:
| > a hypothesis is simply a statement that is true or
| false.
|
| No, that is a _proposition_ , not a hypothesis.
|
| And the requirement that hypotheses be explanatory has
| nothing to do with culture, it is the distinguishing
| feature of the scientific method. See:
| https://blog.rongarret.info/2024/03/a-clean-sheet-
| introducti...
| ninetyninenine wrote:
| False. At the very technical level, a hypothesis is
| defined by statistics.
|
| https://www.sciencedirect.com/topics/mathematics/statisti
| cal....
|
| When you cut through all the cultural and human stuff we
| place around the scientific method, in the end it is a
| statistics problem at the most technical level.
| Everything else makes it fuzzy and hard to define.
| abeppu wrote:
| You started by saying that in science you cannot prove
| things, only provide evidence, but that in math you can
| prove things.
|
| Then you made an assertion that a hypothesis "is a
| statement that can be true or false. That's it."
|
| Now, you're asserting that a hypothesis "is defined by
| statistics". Never mind that humans did a bunch of
| science before statistics were developed, this is
| different than your prior statement ("true or false.
| That's it."), and you seem extremely confident in it.
|
| You're acting as if you have certainty in a statement,
| but you did not arrive at it by a proof. You've claimed
| that only the falsifiability of a statement matter, not
| its explanatory structure, but your own statements about
| hypotheses are structural and definitional ("defined by
| statistics", "at the most technical level", "ignoring all
| the cultural stuff"). You've asserted that a hypothesis
| is falsifiable, and intrinsically statistical, but you
| bring no quantitative data in support of this.
|
| I don't know what activity you're engaged in, but it
| doesn't seem like a rigorous and principled search for
| truth. And you seem to be more willing to preach about
| the importance of falsifiability than to apply that
| concept critically.
| ninetyninenine wrote:
| >Then you made an assertion that a hypothesis "is a
| statement that can be true or false. That's it."
|
| Yeah so? You can make a statement and the actuality of
| that statement is either true or false. But how you prove
| that statement to be true is NOT possible. That is my
| claim. I am also saying it is POSSIBLE to falsify the
| statement aka disprove it... All statements have this
| property.
|
| >Now, you're asserting that a hypothesis "is defined by
| statistics". Never mind that humans did a bunch of
| science before statistics were developed, this is
| different than your prior statement ("true or false.
| That's it."), and you seem extremely confident in it.
|
| Well you're using the "what came first argument" to say
| that the original scientific definition came before the
| statistical definition so it's more valid. I disagree.
|
| Language emerges from concepts in attempt to explain
| things we only have vague understanding of. Concepts like
| Life and intelligence are ill defined and used for
| communication on topics we don't completely understand.
| It's useful to communicate this way but it's useful only
| because either we don't understand something completely
| or because we use it as a shortcut. Usually a new word
| starts off in this fuzzy state and as we understand
| things better the word takes on a more rigorous
| definition. Science started out without us understanding
| statistics, so that's why you have a lot of older
| definitions attached to it. The technical definition of
| hypothesis is part of mathematics. That is ultimately the
| most correct definition but it's not the definition with
| the most utility. If push comes to shove and we want to
| categorize a technical concept like computer science,
| then the technical definition is what matters more.
|
| >You're acting as if you have certainty in a statement,
| but you did not arrive at it by a proof.
|
| What. I never said this. You are entirely
| misunderstanding. I said statements can either be true or
| false. The proof of whether it's actually true or false
| is a separate issue. My original claim is that proving
| something true is impossible.
|
| >You've claimed that only the falsifiability of a
| statement matter, not its explanatory structure, but your
| own statements about hypotheses are structural and
| definitional ("defined by statistics", "at the most
| technical level", "ignoring all the cultural stuff").
|
| I didn't say only the falsifiability of a statement
| matters. I never said this. I said falsifying a statement
| is the only thing we logically have the ability to do. It
| still matters to do correlations and other types of
| things related to science but at a technical level we
| aren't proving anything. At a technical level things can
| only be falsified. This is not to say OTHER things don't
| matter. They do matter.
|
| >You've asserted that a hypothesis is falsifiable, and
| intrinsically statistical, but you bring no quantitative
| data in support of this.
|
| Did I not post a link to a resource stating this? This is
| Data supporting my point. If you want quantitative data
| for the English definition a word, I'm sorry but that's
| just not physically possible. English definitions cannot
| be quantified into numbers for any meaningful numerical
| analysis.
|
| I know your question is just sort of rhetorical.
| Basically you think I'm being too pedantic and you're
| trying to illustrate a contradiction in my own logic. I
| don't deny it. In the end I'm using my own personal
| opinion here. But I share my opinion here because I
| believe if that the MAJORITY of people completely
| UNDERSTAND what I'm saying they will AGREE with me.
| That's all. But again opinion. And either way nothing can
| really be proven can it? Especially for english
| definitions.
|
| >I don't know what activity you're engaged in, but it
| doesn't seem like a rigorous and principled search for
| truth. And you seem to be more willing to preach about
| the importance of falsifiability than to apply that
| concept critically.
|
| What are you trying to say here? This is false. And it
| approaches the point of accusatory and a lie. I don't
| preach the importance of falsifiability. I am just saying
| that is the only possible technical thing we can do in
| terms of determining if something is true or false. I get
| technical because we ARE CATEGORIZING technical concepts
| and definitions so it's appropriate to DO THIS. If we are
| casually conversing or trying to understand concepts then
| of course we can revert to the more laid back way of
| communicating and fuzzy way of defining things.
|
| But what's actually going on here is that we are
| determining whether or not a technical concept:
| "Theoretical computer science" is math or not? Such
| detailed and rigorous categorization REQUIRES the use of
| detailed and rigorous definitions.
| Koshkin wrote:
| > _You can make a statement and the actuality of that
| statement is either true or false._
|
| It can also be "not even wrong."
| ninetyninenine wrote:
| What does that mean? How does "not even wrong" differ
| from true or false?
| Koshkin wrote:
| https://en.wikipedia.org/wiki/Not_even_wrong
| lisper wrote:
| Now you're moving the goal posts. First, it was "a
| hypothesis is a statement that can be true or false.
| That's it." Now it's "a hypothesis is defined by
| statistics". Get back to me when you've decided what your
| position actually is. I'm not going to waste time
| debunking every half-baked idea you can come up with.
| ninetyninenine wrote:
| The goal posts were never moved. What moved is your
| understanding of what I'm trying to say.
|
| A hypothesis is a statement that is TRUE or FALSE. And
| THIS is HOW it's defined by statistics.
|
| >I'm not going to waste time debunking every half-baked
| idea you can come up with.
|
| I'm sorry but this attitude is offensive and against the
| rules here. I can't participate in any further discussion
| with you because of this. Thank you for your time and
| good day.
| Koshkin wrote:
| I don't think that physics (for example) uses the word
| "hypothesis" in the same sense, even though there are,
| indeed, parallels between the two sciences.
| ninetyninenine wrote:
| What is the physics definition and what sciences are you
| referring to?
| SkyBelow wrote:
| I think part of the problem is when we compare the two
| following.
|
| Engineering - Physics - Math
|
| Computer Engineering - Computer Science
|
| Notice that the second only has two steps? Engineering isn't
| really science, but there is a sort of science. Now one will
| be quick to point out that computer engineering does depend
| upon physics (and chemistry, and even a wee bit of biology
| and higher). But I think Computer Science is large enough in
| scope it contains true Computer Science, which is as much
| math as math is, but it also contains more real world test
| and verify parts of computing. Things that might be able to
| fit up under physics or chemistry, but which ended up being
| placed under computer science.
|
| If we are talking a Turing machine, that is math (or
| something equivalent to math). If we are talking about how a
| compiler can optimize code by rewriting some things to be
| computational equivalent but to put operations in an order
| that most CPUs can run faster, that feels like we've stepped
| into science. We've overloaded the terminology and now have
| some linguistic debt that needs paying off.
|
| I sometimes joke that my undergrad degree in Computer Science
| involved only a single class in Computer Science.
| jltsiren wrote:
| If you define science in terms of the scientific method, you
| make it a fundamentally useless hobby that can never produce
| anything of value. If falsifying hypotheses is all you can
| do, you can never create the kind of knowledge others can
| build on. The part of science that creates value is building
| models and explanations that can make reliable predictions.
| And that can be used as building blocks of more elaborate
| models and explanations for more complex phenomena.
|
| In theoretical computer science, design and analysis of
| algorithms is the study of algorithms as mathematical
| objects. The unfortunately named algorithm engineering is the
| science of algorithms. It deals with algorithms that are
| written in code and run on real computers. Among other
| things, it seeks to build models that can predict the
| performance of an algorithm without implementing and running
| it.
|
| Then there is algorithmic economics (or whatever it's called
| today), which was a huge success for theoretical computer
| science. At least in some amoral sense. The microeconomic
| models it created enabled turning the internet into the ad-
| centric data-driven dystopia it currently is.
| ninetyninenine wrote:
| >If you define science in terms of the scientific method,
| you make it a fundamentally useless hobby that can never
| produce anything of value. If falsifying hypotheses is all
| you can do, you can never create the kind of knowledge
| others can build on. The part of science that creates value
| is building models and explanations that can make reliable
| predictions. And that can be used as building blocks of
| more elaborate models and explanations for more complex
| phenomena.
|
| You don't define it this way in common parlance or even in
| articles. But you do need to heavily define it this way
| when categorizing things. If you don't do this you have a
| categorical mishmash where nothing is ever truly defined
| properly and filled with fuzzy meanings. See the word
| "entropy" there are at least 3 definitions for that word
| and these definitions confuse people and lead most people
| to not completely understand the concept of what entropy is
| EVEN at just an intuitive and fuzzy level.
|
| I realize it appears that I'm being overly pedantic and
| inflexible but this is NOT the case.
|
| To be flexible means you need to understand why language
| SHOULD NOT have rigid definitions in certain contexts but
| also WHY it should be extremely rigid and concrete in other
| contexts. You need BOTH. When it comes to categorization on
| what is "theoretical computer science" and other very
| technical topics we Need to have well defined categories
| and definitions.
|
| The fuzziness of literature and poetry which remains open
| to interpretation has significantly lower utility in
| technical fields.
| jltsiren wrote:
| Now you are assuming that rigidly defined science is a
| useful category. I'm less sure about that. It's certainly
| not a universal category, as the concept does not even
| exist in many European languages. Instead of "science",
| they have something like "Wissenschaft". It has retained
| the original wider meaning, while English "science" has
| narrowed in scope. There can be subdivisions such as
| "naturvetenskap", but they are typically defined by the
| topic of study rather than the methods used.
| ninetyninenine wrote:
| >Now you are assuming that rigidly defined science is a
| useful category. I'm less sure about that.
|
| It's useful for categorization (which is the overall
| topic). For formalization of concepts. Formalization is
| always useful for technical concepts. Programming is one
| of those things that requires formal definitions.
|
| It's probably less useful for common communication. But
| that's not what I'm referring to. Sure in communication
| we don't require technical definitions. I'm not arguing
| for whether MY definition has utility in a variety of
| contexts.
|
| I'm simply saying for the rigorous categorization being
| performed by the OP on what "theoretical computer
| science" is.... he should ALSO use the rigorous
| definitions of the Categories themselves.
| nonameiguess wrote:
| 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.
| youoy wrote:
| > 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...
| bbor wrote:
| 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 wrote:
| 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_ca
| lcu...
| calf wrote:
| 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
| hrkucuk wrote:
| >"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 wrote:
| 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 wrote:
| 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 wrote:
| 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.
| throw_pm23 wrote:
| It becomes clearer if you check out the entire quote from von
| Neumann:
|
| .. mathematical ideas originate in empirics, although the
| genealogy is sometimes long and obscure. But, once they are so
| conceived, the subject begins to live a peculiar life of its
| own and is better compared to a creative one, governed by
| almost entirely aesthetical motivations, than to anything else
| and, in particular, to an empirical science. There is, however,
| a further point which, I believe, needs stressing.
|
| As a mathematical discipline travels far from its empirical
| source, or still more, if it is a second and third generation
| only indirectly inspired by ideas coming from "reality," it is
| beset with very grave dangers. It becomes more and more purely
| aestheticizing more and more purely l'art pour l'art. This need
| not be bad, if the field is surrounded by correlated subjects,
| which still have closer empirical connections, or if the
| discipline is under the influence of men with an exceptionally
| well-developed taste. But there is a grave danger that the
| subject will develop along the line of least resistance, that
| the stream, so far from its source, will separate into a
| multitude of insignificant branches, and that the discipline
| will become a disorganized mass of details and complexities. In
| other words, at a great distance from its empirical source, or
| after much "abstract" inbreeding, a mathematical subject is in
| danger of degeneration. At the inception the style is usually
| classical; when it shows signs of becoming baroque, then the
| danger signal is up. It would be easy to give examples, to
| trace specific evolutions into the baroque and the very high
| baroque, but this, again, would be too technical.
|
| In any event, whenever this stage is reached, the only remedy
| seems to me to be rejuvenating return to the source: the
| reinjection of more or less directly empirical ideas. I am
| convinced that this was a necessary condition to conserve the
| freshness and the vitality of the subject and that this will
| remain equally true in the future.
| PeterStuer wrote:
| 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 wrote:
| 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 wrote:
| But how is that supported by TCS?
| pmontra wrote:
| 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 wrote:
| How about we start by introducing time, interactions with
| things exterior to the subsystem modeled?
| GenericCanadian wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| '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 wrote:
| The Turing machine is an artificial system constructed to be
| easy to reason about. The computer on my desk is most certainly
| not!
| cjfd wrote:
| Well, it depends. Have you ever considered writing a word
| processor in a Turing machine?
| anthk wrote:
| Not a Turing Machine, but with a Lisp interpreter and few
| atoms (Lambda Calculus in the end) you can state the peano
| axioms, then a basic arithmetic calculator, and after that,
| a basic algebra solver in minutes.
|
| https://justine.lol/sectorlisp2/
| RandomThoughts3 wrote:
| The Turing machine is a realisation of what a computing
| machine could be in a logical sense. It's not so much
| constructed to be easy to reason about as to be the simplest
| form of what such a machine could be.
|
| The fact that functions computable with such a machine is
| equivalent to functions computable in the lambda calculus and
| Herbrand general recursive functions is the remarkable
| results.
|
| The fact that it can somehow be linked to an actual computing
| machines outside of logic is merely a happy accident.
|
| Having said that you could think I disagree with Vardi but
| the truth is: I think the point he brings is just void of
| substance. That's only of interest to people who like
| university politics and how departments hire. It's of no
| impact to the field whatsoever. Why does it matter what is or
| isn't semantically TCS and if it is or not mathematics? The
| problems will still be there the same.
| anthk wrote:
| On Lambda Calculus:
|
| https://justine.lol/sectorlisp2/
|
| Also, the original paper on Lisp it's beauty itself. It's
| describing Lisp... in Lisp, recursively stating both (eval)
| and (apply). Magic.
| peterkos wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 "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."
| booleandilemma wrote:
| Why do you write like this?
| sampo wrote:
| > 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 wrote:
| 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.
| epgui wrote:
| 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.
| pron wrote:
| > 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 wrote:
| it's when I'm a computer scientist, theoretically
| bbor wrote:
| 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 wrote:
| 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 wrote:
| 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
|
| [2] https://en.wikipedia.org/wiki/Trinity_(nuclear_test)
|
| [3] https://amturing.acm.org/award_winners/dijkstra_1053701.cfm
| oglop wrote:
| 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 wrote:
| > 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 wrote:
| 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.
___________________________________________________________________
(page generated 2024-10-18 23:01 UTC)