As you probably already know from other sources, Martin Davis passed away on Jan 1, 2023, at the age of 94. His wife Virginia died a few hours later.
He majored in math at Brooklyn College and graduated in 1948.
He got his PhD under Alonzo Church at the Princeton in 1950.
Two years for a PhD seems fast!
His Phd was on Recursion theory.
In it he conjectured that Hilbert's tenth problem (below) is undecidable.
He is known for the following (if you know more, please leave a comment).
1) Hilbert's Tenth Problem.
Hilbert posed 23 problems in the year 1900 for mathematicians to work on
over the next 100 years. Hilbert's tenth problem, in modern terminology, was
Find an algorithm that will, given a polynomial p \in Z[x_1,...,x_n],
determine it has a Diophantine solution (that is, a_1,...,a_n\in Z
such that p(a_1,...,a_n)=0).
In Hilbert's article he did say in a preface to all of the problems. Here is the exact quote:
Occasionally it happens that we seek the solution under insufficient hypotheses or in an incorrect sense, and for this reason do not succeed. The problem then arises: to show the impossibility of the solution under the given hypotheses or in the sense contemplated.
Hilbert had hoped that this problem would lead to deep results in number theory. And it has to some extend. However this went from being a problem in number theory to a problem in logic. That might not be quite right: the result did use number theory.
In 1961 Davis-Putnam-Robinson showed that the problem is undecidable IF you also allow exponentials. This may have been a turning point for the conventional wisdom to shift from `Probably Solvable' to `Probably Unsolvable.'
Martin Davis predicted that the H10 would be shown undecidable by a young Russian by the end of the decade. He was correct. Yuri Matiyasevich did indeed prove H10 undecidable in 1970. By all account Davis was delighted. When the result is cited usually all four people are credited which is as it should be. He wrote an excellent exposition of the complete proof from soup to nuts in:
Hilbert's tenth problem is unsolvable, American Math Monthly, Volume 80, No 4, 233-269.
When I first heard of this result I assumed that the number of variables and the degree to get undecidability was huge. I was wrong. I wrote a survey of H10 emphasizing what happens if you bound the degree and the number of variables, see here
2) SAT Solvers. Davis-Putnam-Logemann-Loveland outlined a SAT Solver, or really a class os SAT Solvers. While I doubt it was the first SAT Solver, it was an early one that tried to cut down on the time needed.
3) He wrote the following books:
Computability and Unsolvability (1958, reprinted 1982)
Applied Non-Standard Analysis (1977, reprinted 2014)
Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science (1994 (with Elaine Weyuker)
The Universal Computer: The Road from Leibniz to Turing (2000, reprinted as
Engines of Logic: Mathematicians and the origin of the computer)
The Undecidable: Basic Paper on undecidable propositions, unsolvable problems and computable functions (2004)
4) He was a recursion theorist who could actually program a Turing Machine to really do things. There are still some people who do that- getting the UTM down to a small number of states, and the work (the Wolfram Challenge), and the Busy Beaver Function (see Scott Aaronson's open problems column here,
but I think this is done less by academic recursion theorists than it used to be. I do not have my students in Automata Theory write any TM code. Clyde Kruskal, who had that same course from Martin Davis, thinks that I should.
4) For more on Martin Davis see this obit here and/or his Wikipedia page here
Thank you for this news. I for one did not know it. Very sad. (By the way, for some reason in the first half the formatting is that every sentence is its own paragraph.)
ReplyDeleteThank you also for mentioning "The Universal Computer: The Road from Leibniz to Turing." One of his contributions that may be undervalued is the ability to understand exactly what is the point at issue, and to clearly state it, so that others of us can also understand that. In my Theory class I urge that book on my students.
Your dates for Davis's undergrad and PhD degrees seem to be wrong. According to your own wikipedia link, he got his bachelor's degree in 1948 and his PhD in 1950 (in 2 years, not 3). These dates (and the 2-year PhD) also seem to be confirmed in this interview (https://www.ams.org/notices/200805/tx080500560p.pdf).
ReplyDeleteThanks, fixed
DeleteAlso he got his PhD at Princeton, not Chicago.
ReplyDeleteI would like to mention to his credit, three more biographical things:
ReplyDelete1. He is the one who named it the "Halting Problem" from his 1958 text. Turing originally called these things "circular", "circle-free", and "satisfactory".
2. He wrote "Solvability, Provability, Definability: The Collected Works of Emil L. Post", which includes several pages of a kind of obituary or biography of Emil Post. He mentions what it was like as an undergraduate taking a class with Post.
3. He wrote the foreword to "Hillbert's 10th Problem" by Matijasevich (1993), In there, he describes his history and contribution to solving the problem.
thanks, fixed
DeleteAs an older bloke who learned assembler early on (1971: IBM 1130, 1972: CDC 3600, 1973: PDP-6), I worry that younger comp sci. folks may not have good intuitions about what computation is about, so count me in as thinking theory courses should insist that students write Turing machine programs.
ReplyDeleteThe 1st Edition of Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science is 1983 (not 1994). The 2nd edition (1994) has Ron SIgal as a co-author.
ReplyDelete