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.