Sunday, March 20, 2016
Hilary Putnam passed away on March 13
Hilary Putnam passed away on March 13, 2016. Some of the obits say he was a philosopher, mathematician, logician, and computer scientist.
He is probably best known to readers of this blog for his work on Hilbert's 10 problem and resolution.
HILBERT TENTH:
Recall H10 stated in current terminology: Find an ALGORITHM that will, given a poly p(x1,,...,,xn) in many variables, with coefficients in the integers, determine if it has a diophantine solution.
Martin Davis, Hilary Putnam, and Julia Robinson showed that if you also allow exponentation then the problem is undecidable in the early 1960s. Yuri Matijasevich in 1970 showed how to express exps in terms of polynomials to complete the proof. The solution to Hilbert's 10th problem is often credited to all four of them which seems right to me.
One consequence of there proof: for any c.e. set A there is a poly p such that
A = { x | exists x1,...,xn p(x,x1,...,xn)=0}
Later work got the polynomial down to 13 variables.
RESOLUTION:
John Robinson (but see comments) and later papers by Davis-Putnam aad later Davis-Logemann-Loveland devised resolution theorem proven which is an early SAT-solver algorithm. Many modern algorithms are based on it. (Note- earlier version of this post had mistakes in it. I thank Paul Beame's comments below for clarifying the history.)
HOW TO CLASSIFY HIM:
I suspect that Hilary Putnam would call himself a philosopher since that was his MOTIVATION. That may be the best way to classify people (if we are inclined to do that), don't look at WHAT they do look at WHY they do it.
PHIL OF MATH- one problem with Philosophy, even Phil of Math, is that its hard to have well defined questions and therefore hard to answer them. I am NOT criticizing the field, just saying why I would have a hard time working in it.
Subscribe to:
Post Comments (Atom)
Hilary Putnam was a fully-rounded intellectual of a sort that our 21st century society seems no longer to value or produce.
ReplyDeleteHe was grounded in both mathematics and philosophy. I recall in the 1990's, at roughly the same time he was pointing out mathematical fallacies in Roger Penrose's interpretations of the implications of Godel incompleteness in the "The Emperor's New Mind", Putnam was producing his work on a basis for ethics without methaphysical assumptions, "Ethics without Ontology".
Some corrections: Actually Julia Robinson should get the credit for introducing resolution, though clearly the Davis-Putnam paper made it a fully specified algorithm for first-order logical inference. Also, the second SAT-solver paper did not have Putnam as an author (it was just Davis-Logemann-Loveland). DPLL is a combination of the author lists of the two papers and became the norm for a reference in part because many authors had incorrectly referred to the latter as the Davis-Putnam algorithm and in part because the DLL paper was presented merely as an optimization that applied the same resolution and unification over propositional atoms derived from the Herbrandt expansion that appeared in the Davis-Putnam paper.
Didn't John A. Robinson introduce resolution?
ReplyDeletePaul and Anonymous.
ReplyDeleteWikipedia says John Robinson so I have changed my post
Paul- do you have a different source that says it was Julia Robinson?
For a proper tribute/obit, see http://www.huffingtonpost.com/martha-c-nussbaum/hilary-putnam-1926-2016_b_9457774.html
ReplyDeleteDavis and Putnam introduce Device-Putnam Procedure for proving theorems (1960) which is deterministic. They proved it is logically complete.
ReplyDeleteRobinson generalized that and made it nondeterministic (1965) and defined what we call Resolution.
The part which is confusing is that Robinson name is stated as JA Robinson and it is not clear if it is Julia Hall Bowman Robinson who uses J Robinson. Based on that and the affiliation stated on the article it seems it is not Julia Robinson but a different Robinson.
http://dl.acm.org/citation.cfm?id=321253