Somehow philosophy rings a negative connotation in my mind -- a field that indulges in deliberation and debate, and clearly lacks the formalism and rigor that is well and truly the hallmark of theoretical computer science. maybe mathematics of computing would be more appropriate! that would in my opinion be closer to reality
Agree word-to-word with nicertry. Philosophy leaves a negative impression with me, something that involves a lot of handwaving. I was going to suggest 'mathematics of computing' too.
But now that I think of it, there is something a little off in that -- the focus of theoretical cs is to explain the computational phenomena; mathematics is just a tool to the end. Historically, this is perhaps one reason why tcs comes under the category of applied mathematics in many university curricula. But then again, "applied mathematics" does not do justice to what theoretical cs is actually about -- the title focuses more on the tool, than on the goal itself.
Two very good points. Let me pick up where vinodv left off and make a case for why my term might be appropriate.
First, a lot of TCS is deliberation and debate as well. In my field, certainly, half the time is spent making and arguing about definitions. When we prove a theorem we often need a few paragraphs about "what does this theorem mean"? How grounded in reality are we? I can't presume to speak for everyone, but my current paper is on the relationship between two worlds, neither of which is our own.
Further, TCS is only a consumer, and not producer of mathematics. It is reasonable to regard the math as purely incidental. I would argue that TCS is an endeavor to understand the computational properties of the universe.
A month ago I would have agreed with nicertry about the nature of philosophy. But now I have a somewhat better understanding of it than I did, it doesn't seem all that vague to me. For instance, on reading about the philosophy of language
, my first reaction was "what's the earthly use of that?" But on a closer look, I realized that many of the questions considered are the same as or similar to what we looked at in knowledge representation class! It is simply that the people studying the philosophy of language appear to have little background in science or linguistics for that matter, and therefore their methods are foreign to you and me.
This is in fact a criticism that I have long leveled against philosophers in general. In the fine tradition of one of the Greek philosophers (I believe it was Aristotle) who believed that all the laws of physics could be derived from thought alone, most philosophers appear to feel no need to be informed by observation. While it is perfectly fine for philosophers to debate the question "what does foo mean?", the minute they wish to consider the question "how does foo happen in the universe?", it is meaningless to attempt to answer it without the aid of the empirical method. When I read philosophy papers on consciousness, I feel like screaming "open a neuroscience textbook!" I would really like to hear an argument from a philosopher against this charge.
Anyway, I appear to have run aground; the point I was trying to make was that it is not the nature of philosophy itself to reject concreteness - that is simply one approach. Mathematical formulation is an equally valid approach to the philosophy of computing.
Quick comment on one of your points: TCS is probably right now predominantly a consumer of mathematics; it is too young. This is a point of hot debate among theoreticians right now, but let me just remark that TCS *has* made some contributions *to* mathematics proper, so that the relationship is symbiotic - for instance, some theorems in algebraic topology, admittedly application-oriented and small in number, were proven because of its applications to proving circuit lower-bounds.
Your comments strike me as a little strange to me.
"It is simply that the people studying the philosophy of language appear to have little background in science or linguistics for that matter, and therefore their methods are foreign to you and me."
Like Chomsky? Pinker?
"I would really like to hear an argument from a philosopher against this charge."
I think you must be reading the wrong books. There are plenty of people studying consciousness empirically, and who are using cognitive science to synthesize new philosophical theories of consciousness. Christof Koch, Pat and Paul Churchland, Daniel Dennett, and Steven Pinker immediately spring to mind. Even those who aren't in the materialistic reductionist camp (like David Chalmers) tend to be well-versed in the relevant empirical facts.
I think I've read all those authors. They're all great. Chalmers somehow leaves me with a bad feeling, almost as if he is a dualist.
Until I read your post I thought the Churchlands were scientists. I googled them just now and realized they are philosophers. (Until recently I had the same misconception about Dennett.) So it was completely my fault -- due to my biased perception of philosophers as non-empiricists I seem to have subconsciously classified all the empiricists I come across as scientists! Thanks a lot for pointing this out.
P.S: added you. (This probably means there are more math than CS people on my f-list now. I'm sure that's supposed to tell me something, but I can't figure out what :-)
2006-04-25 10:13 pm (UTC)
How the hell do i get the rss feed for a livejournal blog?
- m o c . l i a m g @ i n n u h s e m u
2006-04-25 10:14 pm (UTC)
FF found the atom feed for me.
Stumbled on your LJ from mathematics
. I'm a grad student at A&M in mathematics with a BS in Comp Sci. I agree with your entry. Even undergraduate computer science majors do not understand what computer science is. I would love for undergraduate programs to offer two (or more) distinct majors, differentiating computer programming/software engineering and systems admin from computer science. Part of your frustration is the fault of how computer science departments bill themselves.
Also, CS is just too trendy. A PhD in CS might be a brilliant mathematician, or she might be someone who wrote some lame paper on UI design or something. Mathematics does not have this problem.
I got fed up with those around me complaining about how the material was too "theoretical", so I went into math.
Everyone was always puzzled when I told them I didn't know how to fix their computer.
That's very interesting. I started out trying to get into math and gave it up because I couldn't handle the level of abstraction. I'm actually not too uncomfortable with the hands-on stuff -- my last paper was on cracking passwords, and 'lame' UI design is one of my hobbies.
I don't know what you mean by CS being trendy -- I perceive it as pretty much the opposite of that, at least in America. Enrollment has dropped massively after the bust. But two different undergrad programs makes a lot of sense, especially if the theoretical branch was offered jointly with the math department.
2006-04-30 06:48 pm (UTC)
The present/future of TCS interesection math
I came to stumble upon this blog by chance, was very amused by some of the discussion in this blog. In particular this blog about TCS amused me, so much so that I decided to ask some of the questions I had.
As an applied mathematician/statistician I have only a peripheral understanding of what TCS is all about, though I understand the very basic concepts such as what a Turing machine is and such... Having explained that much, here are my questions addressed to people working the field, hoping that the answers would educate me to learn more about the field.
1. What are the current main/motivating problems in the field, if any, which motivates main stream research? (The only one I know is p = np :) problem ) That brings up the questions of what are the major subfields of TCS which are promising/active?
2. What are the recent ground breaking results? (the examples I am seeking for are the likes of RSA , the recent deterministic, polynomial primality testing, and even my roomie introduced me to this "PCP ")
3. I also know that discrete mathematics has an ongoing symbiotic relationship with TCS.. Is there anything in this front?
hmm what else, oh ya! being from Duke which is very strong on geometry, I know people in Duke who spent all their energy on hopeless problems like the notorious "happy end problem" ( A problem by erdos (but who else!) asking whether n points in general position in space guarantee a convex hexagon?)
Look forward to your answers...
Thanks a lot!
2006-04-30 08:34 pm (UTC)
Re: The present/future of TCS interesection math
And I, in turn, am constantly amused by how many people happen upon my blog and tell me they find it interesting, especially F2F.
There are so many people on my f-list better qualified to answer your questions than I am, but they are probably not reading this discussion, so I will attempt an answer. But before I do, I have to ask if the hilarious double entendre was intentional in your statement
"my roomie introduced me to this PCP."
I'm more of a coke-head myself :)
The core and the bulk of TCS is definitely complexity. The problems that one ultimately seeks to answer are remarkably simple, such as P =? NP, but it turns out that to try to answer it you have to consider (literally) hundreds
of other complexity classes. One typically proves relationships between these classes, most commonly inclusion or separation. Turing machine and circuit classes form the bulk of classes that are considered. There are other classes like branching programs and (especially lately) quantum classes.
If you look at a list of STOC, FOCS or CCC accepted papers, you'll find that 80% of the papers fall into this category. Actually they look like they are constructing algorithms for some problem or showing lower bounds, but you must realize that these are to be interpreted as statements about complexity classes. The remaining 20% are about a variety of things like coding, crypto, protocols, randomness (almost all the papers involve randomness in some form, but most of them can be phrased as questions about complexity classes and so fall under the 80%), data structures etc. There do exist some algorithms papers where the algorithm is intended to be directly interesting because we want to solve the problem in practice. These are typically distributed or network algorithms, because cases where standard Turing machine computations in the real world are suboptimal because we haven't discovered the optimal algorithm yet are practically nonexistent and have been for the last 20 years.
Returning to TM and circuit complexity classes, how does the enormous number of classes arise? We can augment or cripple a TM or a circuit in various ways. One of the most significant ways is randomness (and is in fact perhaps the single main pursuit of recent research. PRIMES is in P for example is a statement about the unnecessity of randomness for PRIMES). Other ways are to restrict the amount of space available, allow TMs to have "advice", allow queries to an "oracle" (which allow us to make statements about our proof techniques), bound the depth of circuits, consider interactive protocols like prover-verifier systems, and various others.
There is another significant branch of TCS that is done more by math people and published in different fora -- logic, computability theory, proof systems, automata etc.
There are a lot of other branches (like AI and VLSI) whose more theoretical practitioners consider themselves TCS people, but our culture
is different from theirs because they don't insist on rigor as much.
As for the recent results, I guess the most recent major one is "L=SL". It'd take a while to explain the major results and why they are significant (and I probably don't understand them very well myself). Let me point you to Lance Fortnow's A Short History of Computational Complexity
. It goes without saying that if you are interested in TCS you should read Fortnow's blog
I should mention that from a theoretical perspective, Diffie Hellman was at least as significant as RSA. And since you mentioned primality in the same sentence, I must point out that it is almost totally unrelated to cryptography.
Finally, I am completely ignorant about the relationship between TCS and math :)
2006-05-06 12:04 pm (UTC)
Re: The present/future of TCS interesection math
Arvind, that was a nice overview.
A quick remark: A major focus of theoretical computer science has been to come up with the right abstractions/definitions for the computational processes that people talk about all the time and take for granted. Three motivating (and highly influential) examples are the ideas of 'randomness', 'proof' and 'knowledge'.
And questions about them such as
1. 'What does it mean for a string to be random' ? (Kolmogorov Complexity)
2. 'What does it mean for an object to look random' ? (Pseudorandomness, and the idea that randomness of an object really depends on the computational ability of the observer)
3. 'Can X prove more theorems to Y by dialogue, than by writing down the proof in a piece of paper' ? (Interactive Proofs)
4. 'When does a conversation involve transfer of knowledge' and before answering that, 'What in the world is knowledge' (Knowledge Complexity and Zero-knowledge)
Computation is such a pervasive and fundamental concept, that I would say computer science (the study of the nature of computation, as opposed to repairing computers, irrespective of what my mom thinks) deserves a place of its own, rather than being delegated as a branch of applied mathematics. Mathematics is but a tool -- a powerful one at that -- that aids us in understanding computation.