Ask HN: Underrated Turing Award Recipients? | Hacker News Reader

Ask HN: Underrated Turing Award Recipients?

10 pointsipnon6 comments

I stumbled on this old book today called "Transaction Processing"[0] that never made it past a first edition in the early 90s. It is a leviathan treatise on the unification of conventional and distributed database systems, operating systems, computer networking and software engineering. How could a book like this end up in the digital dust bin?

I looked up the first author, Jim Gray. Apparently, the guy won the Turing Award in 1998 for "for seminal contributions to database and transaction processing research and technical leadership in system implementation."[1] I studied computer science at university and have never heard of such a thing. Frankly, I am shaken there are still astonishing ideas, like "transaction processing," that hover unnoticed over the ivory towers. What's the point of lofty ideas if everyone doesn't know about them?

Jim Gray seems to have disappeared mysteriously at sea around 10 years after receiving his Turing Award. Now he doesn't appear a widely recognizable name, even among HN. I searched for "Transaction Processing" in the HN archive, but didn't find anything on Jim Gray.

It makes me wonder who else didn't get all their roses when they were due? Who are the underrated Turing Award recipients?

[0] https://www.amazon.com/Transaction-Processing-Concepts-Techniques-Management/dp/1558601902

[1] https://en.wikipedia.org/wiki/Jim_Gray_(computer_scientist)

Jim Gray's New York Times obituary https://bits.blogs.nytimes.com/2008/05/31/a-tribute-to-jim-g...

Looked him up and came across the fact that he evaluated the Club of Rome's overpopulation model and concluded it was wrong [1], and that he eventually (decades later) disappeared at sea. Almost certainly unrelated, but it's hard to escape conspiratorial thinking these days.

Easy one for me: Stephen A. Cook. Proved that SAT was NP-complete and formulated the P vs. NP problem.

IMO, even among Turing Award winners there are tiers, and he's in the top one in my book.

It's a succinct paper. http://4mhz.de/download.php?file=Cook1971_Letter.pdf

I had to google "SAT":

"In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisfies a given Boolean formula. In other words, it asks whether the variables of a given Boolean formula can be consistently replaced by the values TRUE or FALSE in such a way that the formula evaluates to TRUE... For example, the formula "a AND NOT b" is satisfiable because one can find the values a = TRUE and b = FALSE, which make (a AND NOT b) = TRUE. In contrast, "a AND NOT a" is unsatisfiable.

SAT is the first problem that was proven to be NP-complete... This means that all problems in the complexity class NP, which includes a wide range of natural decision and optimization problems, are at most as difficult to solve as SAT. There is no known algorithm that efficiently solves each SAT problem, and it is generally believed that no such algorithm exists; yet this belief has not been proven mathematically, and resolving the question of whether SAT has a polynomial-time algorithm is equivalent to the P versus NP problem..."

https://en.wikipedia.org/wiki/Boolean_satisfiability_problem

https://en.wikipedia.org/wiki/Stephen_Cook

The NP encapsulation diagram is so interesting. From someone who took a few theory classes, but not a ton, it's very interesting and mystifying. One day, I hope there can be some sort of proof for P vs NP, one way or the other. Mostly because it's a problem that is relatively understandable, but crazy to think we don't have an answer. The idea that P=NP would be an incredible proof to see (or watch someone dissect) because (from what I remember from my algo class) that means that all NP problems can be traced to some root problem that can be used to solve it. That root problem would be an incredible thing to see.

If it wasn't obvious, I'm not very knowledgeable on this topic.

Reply on news.ycombinator.com