Martin Davis (mathematician)

Davis died on January 1, 2023, at age 94. His wife died the same day several hours later.

In 1974, Davis won the Lester R. Ford Award for his expository writing related to his work on Hilbert's tenth problem, and in 1975 he won the Leroy P. Steele Prize and the Chauvenet Prize (with Reuben Hersh). He became a fellow of the American Academy of Arts and Sciences in 1982, and in 2013, he was selected as one of the inaugural fellows of the American Mathematical Society.

Davis collaborated with Putnam, George Logemann, and Donald W. Loveland in 1961 to introduce the Davis–Putnam–Logemann–Loveland (DPLL) algorithm which was a complete, backtracking-based search algorithm for deciding the satisfiability of propositional logic formulae in conjunctive normal form, i.e. for solving the CNF-SAT problem. The algorithm was a refinement of the earlier Davis–Putnam algorithm, which was a resolution-based procedure developed by Davis and Putnam in 1960. The algorithm is foundational in the architecture of fast Boolean satisfiability solvers.

Davis's 1958 book Computability and Unsolvability is considered a classic in theoretical computer science, while his 2000 book The Universal Computer traces the evolution and history of computing starting including works of Gottfried Wilhelm Leibniz and Alan Turing. His book The Undecidable, the first edition of which was published in 1965, was a collection of unsolvable problems and computable functions.

Davis was married to Virginia Whiteford Palmer, a textile artist. The couple met during their time in Urbana Champaign and subsequently married in 1951. They had two children. The couple lived in Berkeley, California, after his retirement.

During a research instructorship at the University of Illinois at Urbana-Champaign in the early 1950s, he joined the Control Systems Lab and became one of the early programmers of the ORDVAC. He later worked at Bell Labs and the RAND Corporation before joining New York University. During his time at the NYU, he helped set up the university's computer science department. He retired from NYU in 1996. He was later a member of visiting faculty at University of California, Berkeley.

Davis first worked on Hilbert's tenth problem during his PhD dissertation, working with Alonzo Church. The theorem, as posed by the German mathematician David Hilbert, asks a question: given a Diophantine equation, is there an algorithm that can decide if the equation is solvable? Davis's dissertation put forward a conjecture that the problem was unsolvable. In the 1950s and 1960s, Davis, along with American mathematicians Hilary Putnam and Julia Robinson made progress toward solving this conjecture. The proof of the conjecture was finally completed in 1970 with the work of Russian mathematician Yuri Matiyasevich. This resulted in the MRDP or the DPRM theorem, named for Davis, Putnam, Robinson, and Matiyasevich. Describing the problem, Davis had earlier mentioned that he found the problem "irresistibly seductive" when he was an undergraduate and later had progressively become his "lifelong obsession".

Martin David Davis (March 8, 1928 – January 1, 2023) was an American mathematician and computer scientist who made significant contributions to the fields of computability theory and mathematical logic. He is best known for his work on Hilbert's tenth problem leading to the MRDP theorem. He also advanced the Post-Turing Model and co-developed the Davis–Putnam–Logemann–Loveland (DPLL) algorithm which is foundational for Boolean satisfiability solvers.

Davis's parents were Jewish immigrants to the United States from Łódź, Poland, and married after they met again in New York City. Davis was born in New York City on March 8, 1928. He grew up in the Bronx, where his parents encouraged him to obtain a full education. He received his bachelor's degree in mathematics from City College in 1948 and his PhD from Princeton University in 1950. His doctoral dissertation, entitled On the Theory of Recursive Unsolvability, was supervised by American mathematician and computer scientist Alonzo Church.