10 ms·

My view is quite unconventional, but I believe, computer science is a branch of mathematics that deals with large but finite structures (so they need an algorit

by js8 5y ago

My view is quite unconventional, but I believe, computer science is a branch of mathematics that deals with large but finite structures (so they need an algorithmic description). Compare with most of "legacy" mathematics, which studies countable structures (so the description can use arbitrary series). Of course, there are larger sets, but they mostly serve as a theater (just like countable infinity is just a theater of computer science). Finite sets in the rest of mathematics are sometimes considered uninteresting, but not so in computer science, where only very small sets (roughly of up to 32 elements, all subsets can be easily checked on a typical computer) are considered uninteresting. Good example is number theory, which philosophically considers all natural numbers, regardless of size, to be equal type of objects. In computer science, the (although fuzzy) magnitude of numbers plays much bigger role.

triska 5y ago
This is an interesting view that captures a substantial portion of computer science including also programs and proofs with a short and clear criterion. However, a key drawback of this view is that it undersells the linguistic aspect of computer science which is manifested in the search for suitable programming languages. I think it is justified to regard the design of programming languages as a core area of computer science, and that design space is not finite.
- kn1ght 5y ago
  Programming languages are not full linguistics, at least not yet. We focus primarily on syntax, semantics and pragmatics. All of this, though, is firmly rooted in mathematics, defining grammar as expressions and mathematical relationships. This then enables formal mathematical proofs where we can reason about outcome. I don't know if there exists such search that you mention, or it is more of an optimization of language features to problem space. Perhaps in a future where we're able to program our machines by having a conversation with them...
  - triska 5y ago
    I once read an article suggesting that reading computer code does not activate the regions of the brain that are involved in language processing: https://news.mit.edu/2020/brain-reading-computer-code-1215 https://news.mit.edu/2020/brain-reading-computer-code-1215 This may indicate that the sampled programmers did not program in the way it can be done for example with declarative languages, i.e., primarily as a linguistic activity where we describe what we know about the task. I also like the description in Programming as Theory Building by Peter Naur: https://pages.cs.wisc.edu/~remzi/Naur.pdf https://pages.cs.wisc.edu/~remzi/Naur.pdf The feasibility of this approach may depend on the programming languages one uses.
    - kn1ght 5y ago
      Thanks for the articles. I definitely don't do it the same way I process language. To use the same example- I describe a task unambiguously, which makes it a translation from written text to memory regions or execution paths. It gets more concrete than just what I know about the task. A better parallel would be to writing mathematical formulas. When I process language, I believe, more of my brain is engaged in empathy, in trying to match context, in allowing ambiguity, storing ideas and concepts to be disambiguated at a later point.
    - xwolfi 5y ago
      Yeah I remember that I started reaching my first CS successes once I knew enough of the mathematics and properties of the hardware to "think like a machine" and was trying to explain some of my peers still struggling how to do a more step by step execution in their mind. In hindsight it's clear that you dont tell a story when you program a computer or not the way I'd describe my day or teach my kids about a phenomenon. It feels more like unrolling a tape and executing a receipe in the most simple way you can after you built a mind model of the machine. You mimic an actor maybe, rather than imagine an event ?
      - Peritract 5y ago
        I have a very different experience; when I code, it feels similar to mapping out a conversation or constructing a narrative, and this is how I teach it to my students. I've met people who view it as mathematics or philosophy or a bunch of other things; in the end, I think there is a wide range of valid mental models for how computers function and therefore how to communicate with them.
- seoaeu 5y ago
  A substantial portion of theoretical computer science. There are huge swaths of the field that deal with things like machine learning or distributed systems or computer architecture that don't really fall under that categorization.
otabdeveloper4 5y ago
Yes. Indeed in much of the world outside the USA there isn't even such a label as "computer science"; the stuff that's taught as "computer science" in the USA is taught under some sort of "math" label.
- nosianu 5y ago
  I studied it under the name of "Informatik" (Germany), which seems to be the most commonly used word in Europe. The Wikipedia article for "Computer Science" has relevant information, quote (some line breaks added): In the early days of computing, a number of terms for the practitioners of the field of computing were suggested in the Communications of the ACM—turingineer, turologist, flow-charts-man, applied meta-mathematician, and applied epistemologist. Three months later in the same journal, comptologist was suggested, followed next year by hypologist. The term computics has also been suggested. In Europe, terms derived from contracted translations of the expression "automatic information" (e.g. "informazione automatica" in Italian) or "information and mathematics" are often used, e.g. informatique (French), Informatik (German), informatica (Italian, Dutch), informática (Spanish, Portuguese), informatika (Slavic languages and Hungarian) or pliroforiki (πληροφορική, which means informatics) in Greek. Similar words have also been adopted in the UK (as in the School of Informatics of the University of Edinburgh). "In the U.S., however, informatics is linked with applied computing, or computing in the context of another domain." https://en.wikipedia.org/wiki/Computer_science https://en.wikipedia.org/wiki/Computer_science
- pjmlp 5y ago
  In Portugal, there is some time to spend with such matters during the 5 year long that an Informatics Engineering degree takes (certified by the Engineering Order). Since Bologna, it got levelled to Masters, but most still take the 3 + 2 years, not to be left behind the older generation that had 5 + 2 for Master. So plenty of time to go down into the subjects that USA consider computer science. However for those that want to really go down the rabbit hole of computer science as seen on USA, the appropriate degree is Applied Maths into Computing.
  - tsss 5y ago
thanatos519 5y ago
This is good thinking and I am sad to hear that it is unconventional. And now I'll contradict the part of what you said about finite structures: At a theoretical level, the field deals with infinite structures, namely the Turing Machine tape and infinite time. We use finite Computing Machines to simulate a finite section of that tape in a finite time. Maybe we should call it Turing Machine Science, because we use computers to study the behavior of programs in Turing Machines, just as astronomers use telescopes to study the behavior of atoms in stars and particle physicists use particle accelerators to study the behavior of elementary particles. We will never touch those particles, stars, or Turing Machines, but we can know them, hence the science. Software engineering is like using one's understanding of the emissions of the sun to design better solar panels. Very practical, but you don't use your understanding of gravity-driven fusion reactors every day.
- antonvs 5y ago
  > Maybe we should call it Turing Machine Science Nope. Turing machines are arbitrary and rather unmathematical. The lambda calculus is a much better computational formalism, more mathematically grounded and oriented, with far more direct practical applications.
  - jll29 5y ago
    If you like, we can generalize and call it "computation science" to avoid the focus on the tool/machine in favor of the process.
    - plumeria 5y ago
      https://youtu.be/2Op3QLzMgSY?t=16 https://youtu.be/2Op3QLzMgSY?t=16
    - antonvs 5y ago
      "Computing science" is more commonly used as an alternative, but yes, that approach makes much more sense than focusing on some particular abstraction.
  - 5y ago
siraben 5y ago
> computer science is a branch of mathematics that deals with large but finite structures (so they need an algorithmic description) Another way to put this is that computer science deals with mostly constructive mathematics (more precisely, mathematics that uses intuitionistic logic, the kind that is natural to most programmers and computer scientists anyway). For instance, when you prove the fundamental theorem of arithmetic, you actually can translate that into an algorithm for factorizing numbers into products of powers of primes. And the converse holds too, an algorithm is a proof! If you can give me an algorithm that, given a number n, always produces a prime bigger than n, then that actually witnesses the infinitude of primes. Constructive methods are everywhere in CS, for instance, to prove a proposition P, it's possible in classical math to say "assume (not P) is true, then derive a contradiction, hence P", however that would be really unnatural in CS! You never hear "I want to show an algorithm to solve P exists, let's suppose it's not computable, ... contradiction!", because you don't end up with an algorithm at all (what you proved instead was that it's impossible for an algorithm to not exist, without saying what it is). Likewise, you if want to show some number/program/data structure has the properties you care about you almost always give the description explicitly. For more information, I'd say that type theory is a great intersection of math and computer science in a way that's quite accessible to programmers, since we're already used to this kind of thinking, even if we weren't explicitly taught it.
- Scarblac 5y ago
  Although the standard proof of the incomputability of the halting problem assumes it is computable and then reaches a contradiction. And that's more or less the central proof of everything to do with computability.
  - siraben 5y ago
    That's still constructive. This can be a confusion because there's actually two kinds of contradiction proofs: to show ¬ P, assume P then derive a contradiction (false, ⊥) i.e., ¬ P := P -> ⊥. This is actually just fine and constructive, it's just how you prove a negation. OTOH, there's another kind of contradiction proof: to show P, assume ¬ P, then derive a contradiction (false, ⊥) Written with function notation, this becomes P <-> (¬ P -> ⊥) But if we unfold the definition of negation, we have that P <-> ((P -> ⊥) -> ⊥) The left to right direction holds classically and constructive, but the right to left direction uses double negation, which can is equivalent to the law of the excluded middle, AKA classical reasoning.
maweki 5y ago
I always tell my students that computer science the special subset of math that that is coincidentally "easily" executable on a computer. This subsumes finite structures, parseable Problem descriptions, structured formulas, formalized algorithms, etc.
jltsiren 5y ago
Computer science research is mix of (at least) mathematical, engineering, and scientific traditions that varies by subfield. Among the subfields I'm most familiar with, theoretical algorithms are mostly mathematical, while algorithm engineering is closer to engineering. Data compression has both mathematical and engineering work, while bioinformatics is a mix of all three traditions. It's not always clear what is computer science and what isn't. For example, you can find both mathematicians and computer scientists in theoretical computer science. In bioinformatics, you often see similar work from people with CS and life sciences backgrounds.
- TuringTest 5y ago
  Computer science has two origins, born from electronic engineers who studied the ways to build the physical devices required for computation; and mathematicians who studied the best way to represent the desired computations as configurations on such devices. This double soul still lives as the distinction between hardware and software (though the line can be blurred, with programable microchips like FPGAs or the direct implementation of algorithms on hardware in ASICs). However, there's a general and unified way to define anything computing-related, unifying both traditions: seeing computer science as studying the automatic processing of symbols. I.e., anything that the human mind treats as a symbol with a meaning, that can be represented in physical devices and transformed in a different set of symbols through mechanized processes. This definition widens the scope of comp.sci beyond its origins in representing calculations of physics and maths, to include other fields typically taught in the degree but that people don't think of as computer science: natural language processing, design of viable user interfaces (human-computer interaction), design of adequate programming languages apt for different problems. The most general view of this definition encompasses disciplines far removed from engineering, but which are nonetheless used to expand its frontiers: aristotelian ontology was used to invent object-oriented programming, and is still used to explore the semantic web; or semiotics to explore what ideas can be represented and processed automatically, and the best way to build user interfaces tailored to the way we think.
Jenz 5y ago
There are large and finite structures in mathematics that would be very odd to call computer science. Take group theory and, say, the monster group [1]. [1]: https://en.wikipedia.org/wiki/Monster_group https://en.wikipedia.org/wiki/Monster_group
- bregma 5y ago
  I see nothing odd in calling that computer science. It seems more like hardcore computer science.
  - Jenz 5y ago
    And what then couldn’t be called "hardcore computer science?"
    - TuringTest 5y ago
      I believe the core difference between comp-sci and other math is in taking into account the efficiency of the representation and/or transformation. Thus defining the Monster group is discrete mathematics, but not computer science (or not directly). Finding parts of the Monster groups that can be represented and manipulated by computers would be computer science.
tom_mellior 5y ago
> I believe, computer science is a branch of mathematics that deals with large but finite structures (so they need an algorithmic description). This is a strange claim since the entire field was founded upon the investigation of potentially (and often actually) infinite computations. > Compare with most of "legacy" mathematics, which studies countable structures (so the description can use arbitrary series). Define "most". Do it in a way that makes real and complex analysis and topology (and probably many other branches) the smaller part of mathematics. Most importantly though, my problem with this kind of discussion is that the question itself is meaningless. Not everything can be classified into neat " X is a Y" relationships. Not everything needs to be classified into such relationships. Even if the discussion reached a consensus, that consensus would be meaningless. Computer science is a part of math? OK, but so what? Computer science is not a part of math? OK, but so what? Neither conclusion would tell us anything useful.
- xtiansimon 5y ago
  > “ Not everything can be classified into neat " X is a Y" relationships.” I’m with you on skepticism of the x-is-y relationship; however, I read the comment as comparing math versus computing academics. Then, the so-what answer would be informative for the neophyte or youth who is interested In computing but struggles with mathematics instruction. Right? That’s a real thing in education. In fact I find this to be the principal benefit of online MOOC courses. You can compare styles of instruction, and pedagogy from major universities from across the US (and internationally).
- dahart 5y ago
  > Computer science is a part of math? OK, but so what? Computer science is not a part of math? OK, but so what? Neither conclusion would tell us anything useful. I assumed the implication here is that CS, like math, is considered by many to not be a science, but rather a field of construction based on logic. The obvious problem with calling computer science a science is that it isn’t fundamentally based on measuring empirical evidence of a natural process. Maybe that still lands in the ‘OK, but so what?’ category, on the other hand this has been much discussed re: math, and it may be useful to clarify in what ways CS is not employing scientific method.
twobitshifter 5y ago
Before there was a CS major at many universities you would major in mathematics if you wanted to work with computers. John Kemeny majored in mathematics and taught “Finite Mathematics” while a professor. He saw the application of BASIC not as a new field but as a way to simplify computers so that it wasn’t only mathematicians and scientists who could program them.
- musicale 5y ago
  Dartmouth is an example of a CS department coming out of the Math department rather than the EE department. I tend to think that basic (though probably something like Python/numpy rather than BASIC proper) programming fits well into many math courses. The fact that modern TI calculators can run Python seems to mesh nicely with this. (And classic calculators with BASIC also have a long history.) Math courses often in introduce algorithms for arithmetic and algebraic computation, so some coverage of algorithms as a concept seems to fit as well. > BASIC not as a new field but as a way to simplify computers so that it wasn’t only mathematicians and scientists who could program them. This is a fantastic vision. Of course mathematicians and scientists also benefit from user-friendly languages like BASIC or Python. But the idea that computer programming (and computing in general) could be helpful to undergraduates majoring in humanities and social sciences, and perhaps to the public at large, was probably still a fairly radical idea in the 1960s! Trying to make that happen by creating a programming language that first-year students could learn in an afternoon (or so) was/is a remarkable step toward making that vision real.
wayoutthere 5y ago
> Good example is number theory, which philosophically considers all natural numbers, regardless of size, to be equal type of objects. In computer science, the (although fuzzy) magnitude of numbers plays much bigger role. Somewhat similarly, I have a degree in number theory / modal logic systems that was issued by the philosophy department at my university. The concepts are similar to a CS degree except you get really good at describing the problem because philosophy degrees usually involve a lot of writing.
afpx 5y ago
multiplication is an algorithm.
rapjr9 5y ago
At Dartmouth College, computer science started as a branch of the Mathematics Dept. It was eventually made it's own department (located in a former clinic for the mentally ill, Sudikoff Laboratory which some see as ironic). Now Dartmouth is building a new addition to the engineering building (Thayer School of Engineering) and the Math and Computer Science Dept's will move there. I believe the thinking is that those dept's collaborate so much that having them located in the same complex will be helpful. Much of computer science research is more about applications of computers rather than research into computing itself, though some pure computing theory is still being worked on, and everything is becoming cross disciplinary across many fields. One CS project I worked on was designing a smartwatch for health apps. It involved electronics engineering, operating system development, health applications development, sensor data processing, medical research on senior frailty, gesture UI design, UI usability research, secure wireless data transport and collection and more. It was run by a CS prof though. If you go into CS you can end up working on anything and everything. Another CS robotics project involved electronically herding cattle. Where do cattle fit into CS theory? As end users of computers? :-)
- dhosek 5y ago
  At Harvey Mudd College, when I was there in the 80s, the Computer Science department was part of the Biology department: They had one prof who did CS exclusively, one who did Biology exclusively, and one who did both. The “real” departments, Mathematics, Physics, Chemistry and Engineering all offered the option to do a CS option within them, but one of the cool things about Mudd of that era (I’m not sure how much of this has survived since then), was that you didn’t really do a specialized degree in Math, Physics, etc. but got a good broad education across the discipline.
unknown_apostle 5y ago
Working with coinduction. So that’s not a good definition :-)
btilly 5y ago
Please explain how Dijkstra's _Go To Statement Considered Harmful_ (see https://homepages.cwi.nl/~storm/teaching/reader/Dijkstra68.pdf https://homepages.cwi.nl/~storm/teaching/reader/Dijkstra68.p... for the text) is part of mathematics. Then Knuth's famous reply _Structured Programming with Go To_ (available at http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.103.6084&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.103...) and then the much later follow-up at https://cis.temple.edu/~ingargio/cis71/software/roberts/documents/loopexit.txt https://cis.temple.edu/~ingargio/cis71/software/roberts/docu..., _Loop Exits and Structured Programming: Reopening the Debate_. When you've disposed of those, read the less well-known paper _Programming as Theory Building_ by Peter Naur (see https://pages.cs.wisc.edu/~remzi/Naur.pdf https://pages.cs.wisc.edu/~remzi/Naur.pdf for a link). Are there computer science papers that could fit within mathematics? Yes. Are there important computer science papers that clearly don't? Also yes.
- revnode 5y ago
  I don't think there's necessarily a disagreement here. You're talking about "how" to approach problems and he's talking about "what" the problem space is.
- amelius 5y ago
  Those papers you mentioned are closer to the field of Software Engineering.
  - hnfong 5y ago
    This is basically the True Scotsman argument.
  - btilly 5y ago
    On what basis do you claim that software engineering is not part of computer science? Those papers were all written by professors of computer science and published in journals of computer science. All were cited many times by other papers written by other professors of computer science in other journals of computer science.
MeinBlutIstBlau 5y ago
Legitimate computer science should be about assembly and C for the most part. Knowing mathematically how the 1s and 0s are outputting through the machines circuit. Nowadays it's just an antiquated term for programmer. The average C programmer if wager is above 40 years of age whereas the average python or web dev dev must be pushing late 20s.
musicale 5y ago
> computer science is a branch of mathematics Subject boundaries are arbitrary, but they have a practical implementation in terms of university CS departments. Some CS departments came out of math departments, and some universities have a "Department of Mathematics and Computer Science. The theoretical side of CS does seem like a branch of mathematics. Other CS departments came out of EE departments, and and some universities (MIT, Berkeley) have a "Department of Electrical Engineering and Computer Science." The practical side of CS does seem like a branch of engineering. A number of stand-alone CS departments (Stanford) still seem to be part of the school of engineering, so my vote is for CS as an engineering discipline with a theoretical basis in mathematics (perhaps like information systems or signal processing.) I also like the idea of Caltech's "Computing and Mathematical Sciences," as it seems to bring a lot of computing and applied math under one roof.
mbrodersen 5y ago
It’s the other way around. Infinity can only be defined by using algorithms. Think about Peano numbers for example.
chobytes 5y ago
I think it really depends what part of math and what part of computer science you're talking about. Certainly foundations of computation use finite objects from countable sets... But there is more to CS than turing machines and encodings of numbers. For example: Computer vision, machine learning, data science, cryptography, etc are all rife with infinite objects! Proof assistant software and SMT solvers can also prove things about infinite mathematical structures from number theory, ZFC, topology, etc. Pure mathematics also cares about finite algorithms. Every proof is a finite sequence of deductions on finite objects from a countable set... eg a computer program! Other examples include: computing bounds, integrals, roots of polynomials, divisors, bases, fundamental groups, etc. Pure math is full of computation! tl;dr the line between math and cs is extremely fuzzy.

by js8 5y ago

triska 5y ago

This is an interesting view that captures a substantial portion of computer science including also programs and proofs with a short and clear criterion. However, a key drawback of this view is that it undersells the linguistic aspect of computer science which is manifested in the search for suitable programming languages. I think it is justified to regard the design of programming languages as a core area of computer science, and that design space is not finite.

kn1ght 5y ago
Programming languages are not full linguistics, at least not yet. We focus primarily on syntax, semantics and pragmatics. All of this, though, is firmly rooted in mathematics, defining grammar as expressions and mathematical relationships. This then enables formal mathematical proofs where we can reason about outcome. I don't know if there exists such search that you mention, or it is more of an optimization of language features to problem space. Perhaps in a future where we're able to program our machines by having a conversation with them...
- triska 5y ago
  I once read an article suggesting that reading computer code does not activate the regions of the brain that are involved in language processing: https://news.mit.edu/2020/brain-reading-computer-code-1215 https://news.mit.edu/2020/brain-reading-computer-code-1215 This may indicate that the sampled programmers did not program in the way it can be done for example with declarative languages, i.e., primarily as a linguistic activity where we describe what we know about the task. I also like the description in Programming as Theory Building by Peter Naur: https://pages.cs.wisc.edu/~remzi/Naur.pdf https://pages.cs.wisc.edu/~remzi/Naur.pdf The feasibility of this approach may depend on the programming languages one uses.
  - kn1ght 5y ago
    Thanks for the articles. I definitely don't do it the same way I process language. To use the same example- I describe a task unambiguously, which makes it a translation from written text to memory regions or execution paths. It gets more concrete than just what I know about the task. A better parallel would be to writing mathematical formulas. When I process language, I believe, more of my brain is engaged in empathy, in trying to match context, in allowing ambiguity, storing ideas and concepts to be disambiguated at a later point.
  - xwolfi 5y ago
    Yeah I remember that I started reaching my first CS successes once I knew enough of the mathematics and properties of the hardware to "think like a machine" and was trying to explain some of my peers still struggling how to do a more step by step execution in their mind. In hindsight it's clear that you dont tell a story when you program a computer or not the way I'd describe my day or teach my kids about a phenomenon. It feels more like unrolling a tape and executing a receipe in the most simple way you can after you built a mind model of the machine. You mimic an actor maybe, rather than imagine an event ?
    - Peritract 5y ago
      I have a very different experience; when I code, it feels similar to mapping out a conversation or constructing a narrative, and this is how I teach it to my students. I've met people who view it as mathematics or philosophy or a bunch of other things; in the end, I think there is a wide range of valid mental models for how computers function and therefore how to communicate with them.
seoaeu 5y ago
A substantial portion of theoretical computer science. There are huge swaths of the field that deal with things like machine learning or distributed systems or computer architecture that don't really fall under that categorization.

otabdeveloper4 5y ago

Yes. Indeed in much of the world outside the USA there isn't even such a label as "computer science"; the stuff that's taught as "computer science" in the USA is taught under some sort of "math" label.

nosianu 5y ago
I studied it under the name of "Informatik" (Germany), which seems to be the most commonly used word in Europe. The Wikipedia article for "Computer Science" has relevant information, quote (some line breaks added): In the early days of computing, a number of terms for the practitioners of the field of computing were suggested in the Communications of the ACM—turingineer, turologist, flow-charts-man, applied meta-mathematician, and applied epistemologist. Three months later in the same journal, comptologist was suggested, followed next year by hypologist. The term computics has also been suggested. In Europe, terms derived from contracted translations of the expression "automatic information" (e.g. "informazione automatica" in Italian) or "information and mathematics" are often used, e.g. informatique (French), Informatik (German), informatica (Italian, Dutch), informática (Spanish, Portuguese), informatika (Slavic languages and Hungarian) or pliroforiki (πληροφορική, which means informatics) in Greek. Similar words have also been adopted in the UK (as in the School of Informatics of the University of Edinburgh). "In the U.S., however, informatics is linked with applied computing, or computing in the context of another domain." https://en.wikipedia.org/wiki/Computer_science https://en.wikipedia.org/wiki/Computer_science
pjmlp 5y ago
In Portugal, there is some time to spend with such matters during the 5 year long that an Informatics Engineering degree takes (certified by the Engineering Order). Since Bologna, it got levelled to Masters, but most still take the 3 + 2 years, not to be left behind the older generation that had 5 + 2 for Master. So plenty of time to go down into the subjects that USA consider computer science. However for those that want to really go down the rabbit hole of computer science as seen on USA, the appropriate degree is Applied Maths into Computing.
- tsss 5y ago

thanatos519 5y ago

This is good thinking and I am sad to hear that it is unconventional. And now I'll contradict the part of what you said about finite structures: At a theoretical level, the field deals with infinite structures, namely the Turing Machine tape and infinite time. We use finite Computing Machines to simulate a finite section of that tape in a finite time. Maybe we should call it Turing Machine Science, because we use computers to study the behavior of programs in Turing Machines, just as astronomers use telescopes to study the behavior of atoms in stars and particle physicists use particle accelerators to study the behavior of elementary particles. We will never touch those particles, stars, or Turing Machines, but we can know them, hence the science. Software engineering is like using one's understanding of the emissions of the sun to design better solar panels. Very practical, but you don't use your understanding of gravity-driven fusion reactors every day.

antonvs 5y ago
> Maybe we should call it Turing Machine Science Nope. Turing machines are arbitrary and rather unmathematical. The lambda calculus is a much better computational formalism, more mathematically grounded and oriented, with far more direct practical applications.
- jll29 5y ago
  If you like, we can generalize and call it "computation science" to avoid the focus on the tool/machine in favor of the process.
  - plumeria 5y ago
    https://youtu.be/2Op3QLzMgSY?t=16 https://youtu.be/2Op3QLzMgSY?t=16
  - antonvs 5y ago
    "Computing science" is more commonly used as an alternative, but yes, that approach makes much more sense than focusing on some particular abstraction.
- 5y ago

siraben 5y ago

> computer science is a branch of mathematics that deals with large but finite structures (so they need an algorithmic description) Another way to put this is that computer science deals with mostly constructive mathematics (more precisely, mathematics that uses intuitionistic logic, the kind that is natural to most programmers and computer scientists anyway). For instance, when you prove the fundamental theorem of arithmetic, you actually can translate that into an algorithm for factorizing numbers into products of powers of primes. And the converse holds too, an algorithm is a proof! If you can give me an algorithm that, given a number n, always produces a prime bigger than n, then that actually witnesses the infinitude of primes. Constructive methods are everywhere in CS, for instance, to prove a proposition P, it's possible in classical math to say "assume (not P) is true, then derive a contradiction, hence P", however that would be really unnatural in CS! You never hear "I want to show an algorithm to solve P exists, let's suppose it's not computable, ... contradiction!", because you don't end up with an algorithm at all (what you proved instead was that it's impossible for an algorithm to not exist, without saying what it is). Likewise, you if want to show some number/program/data structure has the properties you care about you almost always give the description explicitly. For more information, I'd say that type theory is a great intersection of math and computer science in a way that's quite accessible to programmers, since we're already used to this kind of thinking, even if we weren't explicitly taught it.

Scarblac 5y ago
Although the standard proof of the incomputability of the halting problem assumes it is computable and then reaches a contradiction. And that's more or less the central proof of everything to do with computability.
- siraben 5y ago
  That's still constructive. This can be a confusion because there's actually two kinds of contradiction proofs: to show ¬ P, assume P then derive a contradiction (false, ⊥) i.e., ¬ P := P -> ⊥. This is actually just fine and constructive, it's just how you prove a negation. OTOH, there's another kind of contradiction proof: to show P, assume ¬ P, then derive a contradiction (false, ⊥) Written with function notation, this becomes P <-> (¬ P -> ⊥) But if we unfold the definition of negation, we have that P <-> ((P -> ⊥) -> ⊥) The left to right direction holds classically and constructive, but the right to left direction uses double negation, which can is equivalent to the law of the excluded middle, AKA classical reasoning.

maweki 5y ago

I always tell my students that computer science the special subset of math that that is coincidentally "easily" executable on a computer. This subsumes finite structures, parseable Problem descriptions, structured formulas, formalized algorithms, etc.

jltsiren 5y ago

Computer science research is mix of (at least) mathematical, engineering, and scientific traditions that varies by subfield. Among the subfields I'm most familiar with, theoretical algorithms are mostly mathematical, while algorithm engineering is closer to engineering. Data compression has both mathematical and engineering work, while bioinformatics is a mix of all three traditions. It's not always clear what is computer science and what isn't. For example, you can find both mathematicians and computer scientists in theoretical computer science. In bioinformatics, you often see similar work from people with CS and life sciences backgrounds.

TuringTest 5y ago
Computer science has two origins, born from electronic engineers who studied the ways to build the physical devices required for computation; and mathematicians who studied the best way to represent the desired computations as configurations on such devices. This double soul still lives as the distinction between hardware and software (though the line can be blurred, with programable microchips like FPGAs or the direct implementation of algorithms on hardware in ASICs). However, there's a general and unified way to define anything computing-related, unifying both traditions: seeing computer science as studying the automatic processing of symbols. I.e., anything that the human mind treats as a symbol with a meaning, that can be represented in physical devices and transformed in a different set of symbols through mechanized processes. This definition widens the scope of comp.sci beyond its origins in representing calculations of physics and maths, to include other fields typically taught in the degree but that people don't think of as computer science: natural language processing, design of viable user interfaces (human-computer interaction), design of adequate programming languages apt for different problems. The most general view of this definition encompasses disciplines far removed from engineering, but which are nonetheless used to expand its frontiers: aristotelian ontology was used to invent object-oriented programming, and is still used to explore the semantic web; or semiotics to explore what ideas can be represented and processed automatically, and the best way to build user interfaces tailored to the way we think.

Jenz 5y ago

There are large and finite structures in mathematics that would be very odd to call computer science. Take group theory and, say, the monster group [1]. [1]: https://en.wikipedia.org/wiki/Monster_group https://en.wikipedia.org/wiki/Monster_group

bregma 5y ago
I see nothing odd in calling that computer science. It seems more like hardcore computer science.
- Jenz 5y ago
  And what then couldn’t be called "hardcore computer science?"
  - TuringTest 5y ago
    I believe the core difference between comp-sci and other math is in taking into account the efficiency of the representation and/or transformation. Thus defining the Monster group is discrete mathematics, but not computer science (or not directly). Finding parts of the Monster groups that can be represented and manipulated by computers would be computer science.

tom_mellior 5y ago

> I believe, computer science is a branch of mathematics that deals with large but finite structures (so they need an algorithmic description). This is a strange claim since the entire field was founded upon the investigation of potentially (and often actually) infinite computations. > Compare with most of "legacy" mathematics, which studies countable structures (so the description can use arbitrary series). Define "most". Do it in a way that makes real and complex analysis and topology (and probably many other branches) the smaller part of mathematics. Most importantly though, my problem with this kind of discussion is that the question itself is meaningless. Not everything can be classified into neat " X is a Y" relationships. Not everything needs to be classified into such relationships. Even if the discussion reached a consensus, that consensus would be meaningless. Computer science is a part of math? OK, but so what? Computer science is not a part of math? OK, but so what? Neither conclusion would tell us anything useful.

xtiansimon 5y ago
> “ Not everything can be classified into neat " X is a Y" relationships.” I’m with you on skepticism of the x-is-y relationship; however, I read the comment as comparing math versus computing academics. Then, the so-what answer would be informative for the neophyte or youth who is interested In computing but struggles with mathematics instruction. Right? That’s a real thing in education. In fact I find this to be the principal benefit of online MOOC courses. You can compare styles of instruction, and pedagogy from major universities from across the US (and internationally).
dahart 5y ago
> Computer science is a part of math? OK, but so what? Computer science is not a part of math? OK, but so what? Neither conclusion would tell us anything useful. I assumed the implication here is that CS, like math, is considered by many to not be a science, but rather a field of construction based on logic. The obvious problem with calling computer science a science is that it isn’t fundamentally based on measuring empirical evidence of a natural process. Maybe that still lands in the ‘OK, but so what?’ category, on the other hand this has been much discussed re: math, and it may be useful to clarify in what ways CS is not employing scientific method.

twobitshifter 5y ago

Before there was a CS major at many universities you would major in mathematics if you wanted to work with computers. John Kemeny majored in mathematics and taught “Finite Mathematics” while a professor. He saw the application of BASIC not as a new field but as a way to simplify computers so that it wasn’t only mathematicians and scientists who could program them.

musicale 5y ago
Dartmouth is an example of a CS department coming out of the Math department rather than the EE department. I tend to think that basic (though probably something like Python/numpy rather than BASIC proper) programming fits well into many math courses. The fact that modern TI calculators can run Python seems to mesh nicely with this. (And classic calculators with BASIC also have a long history.) Math courses often in introduce algorithms for arithmetic and algebraic computation, so some coverage of algorithms as a concept seems to fit as well. > BASIC not as a new field but as a way to simplify computers so that it wasn’t only mathematicians and scientists who could program them. This is a fantastic vision. Of course mathematicians and scientists also benefit from user-friendly languages like BASIC or Python. But the idea that computer programming (and computing in general) could be helpful to undergraduates majoring in humanities and social sciences, and perhaps to the public at large, was probably still a fairly radical idea in the 1960s! Trying to make that happen by creating a programming language that first-year students could learn in an afternoon (or so) was/is a remarkable step toward making that vision real.

wayoutthere 5y ago

> Good example is number theory, which philosophically considers all natural numbers, regardless of size, to be equal type of objects. In computer science, the (although fuzzy) magnitude of numbers plays much bigger role. Somewhat similarly, I have a degree in number theory / modal logic systems that was issued by the philosophy department at my university. The concepts are similar to a CS degree except you get really good at describing the problem because philosophy degrees usually involve a lot of writing.

afpx 5y ago

multiplication is an algorithm.

rapjr9 5y ago

At Dartmouth College, computer science started as a branch of the Mathematics Dept. It was eventually made it's own department (located in a former clinic for the mentally ill, Sudikoff Laboratory which some see as ironic). Now Dartmouth is building a new addition to the engineering building (Thayer School of Engineering) and the Math and Computer Science Dept's will move there. I believe the thinking is that those dept's collaborate so much that having them located in the same complex will be helpful. Much of computer science research is more about applications of computers rather than research into computing itself, though some pure computing theory is still being worked on, and everything is becoming cross disciplinary across many fields. One CS project I worked on was designing a smartwatch for health apps. It involved electronics engineering, operating system development, health applications development, sensor data processing, medical research on senior frailty, gesture UI design, UI usability research, secure wireless data transport and collection and more. It was run by a CS prof though. If you go into CS you can end up working on anything and everything. Another CS robotics project involved electronically herding cattle. Where do cattle fit into CS theory? As end users of computers? :-)

dhosek 5y ago
At Harvey Mudd College, when I was there in the 80s, the Computer Science department was part of the Biology department: They had one prof who did CS exclusively, one who did Biology exclusively, and one who did both. The “real” departments, Mathematics, Physics, Chemistry and Engineering all offered the option to do a CS option within them, but one of the cool things about Mudd of that era (I’m not sure how much of this has survived since then), was that you didn’t really do a specialized degree in Math, Physics, etc. but got a good broad education across the discipline.

unknown_apostle 5y ago

Working with coinduction. So that’s not a good definition :-)

btilly 5y ago

Please explain how Dijkstra's _Go To Statement Considered Harmful_ (see https://homepages.cwi.nl/~storm/teaching/reader/Dijkstra68.pdf https://homepages.cwi.nl/~storm/teaching/reader/Dijkstra68.p... for the text) is part of mathematics. Then Knuth's famous reply _Structured Programming with Go To_ (available at http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.103.6084&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.103...) and then the much later follow-up at https://cis.temple.edu/~ingargio/cis71/software/roberts/documents/loopexit.txt https://cis.temple.edu/~ingargio/cis71/software/roberts/docu..., _Loop Exits and Structured Programming: Reopening the Debate_. When you've disposed of those, read the less well-known paper _Programming as Theory Building_ by Peter Naur (see https://pages.cs.wisc.edu/~remzi/Naur.pdf https://pages.cs.wisc.edu/~remzi/Naur.pdf for a link). Are there computer science papers that could fit within mathematics? Yes. Are there important computer science papers that clearly don't? Also yes.

revnode 5y ago
I don't think there's necessarily a disagreement here. You're talking about "how" to approach problems and he's talking about "what" the problem space is.
amelius 5y ago
Those papers you mentioned are closer to the field of Software Engineering.
- hnfong 5y ago
  This is basically the True Scotsman argument.
- btilly 5y ago
  On what basis do you claim that software engineering is not part of computer science? Those papers were all written by professors of computer science and published in journals of computer science. All were cited many times by other papers written by other professors of computer science in other journals of computer science.

MeinBlutIstBlau 5y ago

Legitimate computer science should be about assembly and C for the most part. Knowing mathematically how the 1s and 0s are outputting through the machines circuit. Nowadays it's just an antiquated term for programmer. The average C programmer if wager is above 40 years of age whereas the average python or web dev dev must be pushing late 20s.

musicale 5y ago

> computer science is a branch of mathematics Subject boundaries are arbitrary, but they have a practical implementation in terms of university CS departments. Some CS departments came out of math departments, and some universities have a "Department of Mathematics and Computer Science. The theoretical side of CS does seem like a branch of mathematics. Other CS departments came out of EE departments, and and some universities (MIT, Berkeley) have a "Department of Electrical Engineering and Computer Science." The practical side of CS does seem like a branch of engineering. A number of stand-alone CS departments (Stanford) still seem to be part of the school of engineering, so my vote is for CS as an engineering discipline with a theoretical basis in mathematics (perhaps like information systems or signal processing.) I also like the idea of Caltech's "Computing and Mathematical Sciences," as it seems to bring a lot of computing and applied math under one roof.

mbrodersen 5y ago

It’s the other way around. Infinity can only be defined by using algorithms. Think about Peano numbers for example.

chobytes 5y ago

I think it really depends what part of math and what part of computer science you're talking about. Certainly foundations of computation use finite objects from countable sets... But there is more to CS than turing machines and encodings of numbers. For example: Computer vision, machine learning, data science, cryptography, etc are all rife with infinite objects! Proof assistant software and SMT solvers can also prove things about infinite mathematical structures from number theory, ZFC, topology, etc. Pure mathematics also cares about finite algorithms. Every proof is a finite sequence of deductions on finite objects from a countable set... eg a computer program! Other examples include: computing bounds, integrals, roots of polynomials, divisors, bases, fundamental groups, etc. Pure math is full of computation! tl;dr the line between math and cs is extremely fuzzy.