Computer Science is Not Math
scott-a-s.com
scott-a-s.com
But we don't start grouping those engineers in with the physicists. We treat those as two separate disciplines. Well, lets keep computer science a theoretical science and call those people who apply those theoretical discoveries engineers. Much neater and cleaner and makes sense to me.
http://mathdl.maa.org/images/upload_library/22/Ford/DonaldKn...
http://awards.acm.org/images/awards/140/articles/7143252.pdf
I think this is one of those places where a word has different meanings to different people and correctness takes a religious quality and fruitful discussion requires telepathy. Also often depending on the resolution of the definition and where a person stands on if the thing and its description can/should be distinguished.
People who say computer science is math I suspect are hard pressed to find anything that isn't. Myself for example, I define math as the maximal object that has something to say - about anything that has structure - in a systematic way. You magnify/exaggerate a certain aspect of the structure you think is key and explore it in a systematic way to gain insight on the whole thing. So while aspects of computer science are more engineering or science than math, I can look at the whole system of doing computer science in an engineer like function as mathematically describable.
You can "craft" a car without knowing a single formula, but that proved to be inefficient.
In programming is kind of the other way around. There is a way to use formal mathematical methods to "engineer" programs, but for general use they seem to be economically "inefficient".
But I would also argue that there may be a way to "experiment" in a similar way physicist do, and it's by looking at "computing" as a phenomenon of the natural world.
Computing can be considered a science similar to phyisics, because it can be seen as laws that describe nature, or more specifically how information is processed in the natural world. This "computing" works at a "higher level" than physics, which studies the laws of the "hardware". The most used example is the DNA, with information in a higher level of abstraction than the chemical physical support.
I always find amusing to imagine what if Newton had developed his theories as a way to solve practical problems instead of trying to explain motion laws[1], and how maybie that's what happened to "computing".
[1](Physics = "Engine Sciences"?)
And in the same way a mechanic uses physical principles (arrived at by way of math), software engineering uses insights, practices, methods, and languages (which are mathematical entities to control a Turing machine) developed by computer science. Computer scientists in turn also learn quite a bit from challenges found and attacked by the engineers.
A few computer scientists I've met have math degrees and they enjoy exploring intersections of discrete math and formal methods; some also do research almost exclusively in engineering / application domains (e.g. computer graphics). And, some engineers I know do quite a bit of graph theorizing before hitting the keyboard (whether they recognize it or not) because it's useful.
A good SE will be a computer scientist when faced with a new, challenging problem and a CS will engineer on occasion to help her research.
My opinion is that education should split computer science into the information theory part and the engineering part. The information theory part might even merge back into the math departments where it came from.
Sure the blacksmith and the SE can build the final products but without the CS or metallurgist to build the foundation they wouldn't have a job.
Then the engineers will complain that "Software Engineering" doesn't have enough rigor to be called engineering. Actually, it's been happening for years.
http://lesswrong.com/lw/9sv/diseased_disciplines_the_strange...
http://en.wikipedia.org/wiki/Curry%E2%80%93Howard_isomorphis...
Edit: This is exactly what the author is arguing against. Yes, you're writing a proof, but that's not the point of what you're doing at all.
Saying that computer science is not mathematics because it involves real world complications, is like saying that experimental physics isn't physics because it is not done by theorists.
However, programming in general is simply not like that, and programming in general does not, to me, seem to be anything like doing math.
And since that's a very personal statement, let me add by way of context that I have a PhD in math, I have programmed for a living, and I have written computer verified proofs.
It seems to me that most of the people who claim that "programming is math" (and there are many, but perhaps not as many as the OP is implying) have never actually done any math at an advanced level.
I'd be happier saying that programming is a lot like doing word problems, where it's essential not only to get the right answer, but also to use the the right terms, with the right grammar, and in a limited amount of space.
And it's pass/fail.
Hi Colin, can you substantiate that? PhD in CS here and I've done some pretty hardcore math in my academic life.
After writing lots of proofs and lots of programs the two activities don't seem that dissimilar. They are very different "programming languages" indeed, but debugging, modularity, recursion are important for both activities. To give a more concrete example: for my thesis I've implemented at one point a geometric algorithm. Some of the computer code proved buggy so I went to the white board and simply increased the complexity of the math formulas, which allowed me to write less code. I don't see an immense difference between this and, say, combining C and Python code in the same project.
>> programming in general does not, to me,
>> seem to be anything like doing math.
> Hi Colin, can you substantiate that?
Coming up with proofs of things believed true but not yet proven does not feel to me to be at all, in any way, like programming.
> After writing lots of proofs ...
> I went to the white board and simply increased
> the complexity of the math formulas
As I say, programming feels more to me like solving word problems, and I suspect that most of the divide and argument around this topic is caused by a lack of precision in the definition of "doing math".
Which is ironic.
Edits have been made for clarity.
A calculation is a kind of proof, isn't it? Lots of papers contain theorems and lemmas of the form "f(x) = g(x)". I don't think proving such a formula is the same as applying some well-known algorithm (grocery / restaurant bill).
And doing the kind of calculation that's in the intersection is not then programming. Sometimes in the act of programming you will do some math, but doing the math is enabling the programming. Doing the programming is not doing the math. It's a separate activity and a separate skill.
Of course the boundaries are blurred, but I've honestly seen people write a program to take data from a database, present it nicely on the screen, and then assert that programming is just math. I doubt you're claiming that, but I've seen it claimed, and I think it's not only wrong, but misleading, and demeaning to both subjects.
Sometimes you will use math in programming, and sometimes you will use programming in math. That doesn't mean that either is the other.
And now I'm going to be controversial.
And in case anyone else is still reading, here's a theorem:
Theorem: A prime number can be written as the
sum of two squares if and only if it
is of the form 4k+1 .
The reason this is controversial is that many mathematicians couldn't come up with a proof quickly either. Here's another:
Theorem: A number N is prime if and only if (N-1)!+1 is
a multiple of N.
Given a graph G=(V,E), a proper coloring is an assignment c:V->{1..n} of
integers to vertices such that for every edge (u,v) in E, c(u) != c(v).
(In words, color the vertices so that the endpoints of an edge are always
colored differently).
The "Chromatic Function" of a graph takes the number colors and returns
the number of proper colorings.
Theorem: For every graph, the Chromatic Function of G is a polynomial.
If programming is math, and someone is a programmer, shouldn't they be able to prove these theorems?
========
Disclaimer: This is a stronger position than I'm actually willing to defend, but I'm interested to hear people's views.
ADDED IN EDIT: I've spent way too long on this and have things I must do. I'll return later to check for any replies. I'll also get a HN_Notify email if you do reply. Or email me directly.
I guess the main confusing part about the Howard-Curry isomorphism is that the code / comment conventions are commonly reversed between proofs and programs. Programs show a sequence of actions, and may show machine state in the comments, e.g.
...
x = x * f; //x now contains factorial(n)
...
Proofs show state instead (i.e. the proposition that was proven so far), and may contain the operation in the comments:
...
(x + y) ^ 2 = (x + y) * (x + y)
Using the distributivity of addition:
(x + y) ^ 2 = (x + y) * x + (x + y) * y
...
In either case, you:
- start with an initial state
- choose a sequence of operations from an existing set
- end up with a desired state
If either your program or proof has bugs, there are certain initial states that will break some step in the operation sequence and cause an undesired final state.
Work has taken me away and I can't reply at length. I'm trying to find a math equivalent of FizzBuzz. I still claim programming is not math, and math is not programming. Skills in each can help the other, but aren't necessary.
Engaging in the activity of programming is not "doing math."
I will return to this topic when I can - now is not a good time.
Also, one mathematician that I've worked with would object to calling CS math because he doesn't want it infecting his beautiful discipline!
A proof is a program, but a program is not always a proof (as proofs must terminate).
Take an example as implementing a 3D renderer. A computer scientist might argue that underlaying 3D calculations should be correct. A software engineer might optimize for speed, and simply allow incorrect/imprecise calculations, as long as the rendered result does not look very different.
tl;dr: every study involving computation or programming doesn't need to be in the same department.
But really, all of this is just quibbling about semantics.
In some states it's illegal to say you're an engineer unless you specifically have an engineering degree. Most CS degrees are offered as a science degree with an alternate Software Engineering degree being an engineering degree. There's also a noticeable gap in what you're taught depending on which path you take. Friends of mine who majored in software engineering ended up learning more practical languages, how to use source control, software engineering practices, and never had to take a class related to the theory side of it. Whereas half of my classes were information theory, and abstract or theory based math classes.
Does this make them better programmers because they know more languages and tools? That's subjective. However, there are times when you need a computer scientist and not a software engineer but most companies and even developers themselves couldn't tell you the difference between the two.
Purely hypothetical at this point but suppose you were tasked with creating the first ring based authentication system. This involves a decent understanding of group theory . I don't doubt for a second that a software engineer would be able to accomplish this after first teaching them self about group theory but my first bet would be to go to the person with the CS training. Sure they might not be able to code it as well but once the idea has been developed and proven to be mathematically sound it can just be sent off to the engineer.
And in response to your essay, which by and large was tldr, I don't think many people run around saying that CS is math. Many computer scientists, as I'm quite sure you know, need to model their computable structures formally, show reductions or equivalences to other well-studied constructs, and then use the properties of these constucts to establish the expressiveness/complexity/whatever of their model. If outstanding questions remain then it can motivate basic research into the relevant mathematical field (particularly true with cryptography). These people "do math" - many other's from a CS background don't.