Prof. Leslie Valiant has done awesome work in complexity theory. Among other things, he:
* introduced the notion of #P [1]. Replacing the "Is there any ..." question in an NP problem with "How many ... " makes a problem #P e.g. "Is there any subset in this list of integers that adds up to zero" is an NP problem, "How many subsets add up to zero" is a #P problem. This class also includes the problem of doing exact inference in a general graphical model.
* introduced the "Probably Approximately Correct" notion in machine learning for analyzing various learning techniques. [2]
* with Vijay Vazirani, stated & proved the Valiant-Vazirani theorem [3] that, in essence, showed that the intractability of NP problems is not related to the wide variation in possible solutions for the problem. E.g. the Satisfiability problem could have anywhere from zero to exponentially many solutions, but this variance is not the reason it is hard.
The author of this book was a guest on The Daily Show recently and mentioned that there is an award given to the human who is most convincing to the judges that he or she is a human. (I'm not sure which Turing Test event he was talking about specifically.)
I didn't know or even stop to consider this before, but it is interesting to think about what makes our written speech seem human.
hmmm, i think Turing Awards are more biased towards theoretical contributions to CS (even for systems people). Although Stallman has made great contributions to the field of computing, he isn't an academic CS researcher, so he might not be in the running :/
I thought about that too, so I had checked what ACM said:
"It is given to an individual selected for contributions of a technical nature made to the computing community. The contributions should be of lasting and major technical importance to the computer field"
I think his work with GNU has been one of the most important technical contributions to the community we've seen.
On a non-technical note, his push for free software has also been incredibly influential for the community. While I disagree with a lot of ideology and in particular the ideology behind the GPL personally, I think the world is generally better for it.
I would not be surprised if Maurice Herlihy managed to get a Turing Award in the next few years.
I would be surprised if Stallman got a Turing Award however. I can't think of anything beyond his philosophy that makes him stand out in any technically innovative way.
"Stallman has also developed a number of pieces of widely used software, including the original Emacs, the GNU Compiler Collection, the GNU Debugger, and many tools in the GNU Coreutils."
* introduced the notion of #P [1]. Replacing the "Is there any ..." question in an NP problem with "How many ... " makes a problem #P e.g. "Is there any subset in this list of integers that adds up to zero" is an NP problem, "How many subsets add up to zero" is a #P problem. This class also includes the problem of doing exact inference in a general graphical model.
* introduced the "Probably Approximately Correct" notion in machine learning for analyzing various learning techniques. [2]
* with Vijay Vazirani, stated & proved the Valiant-Vazirani theorem [3] that, in essence, showed that the intractability of NP problems is not related to the wide variation in possible solutions for the problem. E.g. the Satisfiability problem could have anywhere from zero to exponentially many solutions, but this variance is not the reason it is hard.
[1] http://qwiki.stanford.edu/index.php/Complexity_Zoo:Symbols#s...
[2] http://web.mit.edu/6.435/www/Valiant84.pdf
[3] http://www.cs.princeton.edu/courses/archive/fall05/cos528/ha...