Over in this thread, ftg makes the following assertion:
To put it plainly, I disagree. The question at hand is that of the equality of two sets; if that’s not a mathematical question, then what is it?
More generally, I’d like to argue that some subdisciplines of computer science are also subdisciplines of mathematics.
Barring the possibility that my professors have been lying to me, the crux of theoretical computer science is Turing computability. In particular, the sets P and NP are defined in terms of Turing machine computations. From this, it seems sufficient to argue that the theory of Turing machines is mathematical in nature. A Turing machine can be defined as an ordered 7-tuple of sets that satisfy a few axioms. Referring to the standard definitions of set theory (in particular, that of an ordered n-tuple), we have that a Turing machine is a set. The theory of sets is definitely mathematical; therefore, Turing computability is a mathematical theory. Therefore, some subdiscipline of computer science is also a subdiscipline of mathematics.
Clearly, neither discipline is a subdiscipline of the other; however, I think I’ve argued that they do have a non-empty intersection.
I apologize for my inability to find links on the subjects at hand for those who are not familiar with this material. I use books for my information; in particular, I was looking at this book and this book.
I always considered the entirety of Computer Science a subset of Mathematics. Nothing in my college years getting a degree in CS or my subsequent 12+ years in software development has changed my mind.
Not I think about it too much, though. Maybe a counter-example would change my mind.
Personally, I think the “P =? NP” problem should be part of mathematics, because math geeks tend to be much better at doing proofs than computer geeks. Therefore, putting “P =? NP” into the field of mathematics will mean that the problem will be solved much sooner than if we left it in the hands of a bunch of C++ programmers.
And the sooner we either (A) get a proof that NP-complete problems cannot be solved in P time, or (B) come up with a way to turn an NP-complete problem into a P problem, then the sooner we will either be able to sleep better at night (in the case of (A)), or be forced to come up with an encryption scheme whose code-cracking solution lies entirely outside NP (in the case of (B)). Either of these outcomes will be preferable to this no-man’s-land of ignorance we’re wallowing in today!
Has there been any formal study of this? I know that getting people to write readable code is extremely important, but AFAIK we’re just guessing on how to do that (and even on what makes a million-line program readable).