About the Speaker

Martin Davis

Martin Davis is one of the world’s outstanding logicians. He was born in 1928 in New York City, where he attended City College and was influenced by Emil L. Post. Early on Davis came under the spell of Hilbert’s Tenth Problem: Does there exist an algorithm that can, given an arbitrary Diophantine equation, decide whether that equation is solvable? Davis’s PhD dissertation, written at Princeton University under the direction of Alonzo Church, contained a conjecture that, if true, would imply that Hilbert’s Tenth Problem is unsolvable. In rough terms, the conjecture said that any computer can be simulated by a Diophantine equation. The implications of this conjecture struck many as unbelievable, and it was greeted with a good deal of skepticism; for example, the conjecture implies that the primes are the positive part of the range of a Diophantine polynomial. Work during the 1950s and 1960s by Davis, Hilary Putnam, and Julia Robinson made a good deal of headway towards proving the conjecture. The final piece of the puzzle came with work of Yuri Matiyasevich, in 1970. The resulting theorem is usually called either DPRM or MRDP (Matiyasevich favors the former and Davis the latter). The unsolvability of Hilbert’s Tenth Problem follows immediately.

Davis became one of the earliest computer programmers when he began programming  the ORDVAC computer at the University of Illinois in the early 1950s. His book Computability and Unsolvability first appeared in 1958 and has become a classic in theoretical computer science. An early interest in automated deduction in collaboration with Hilary Putnam led to the Davis-Putnam algorithm for satisfiability. Problems with that  algorithm became evident when an implementation of a first order logic prover was attempted working with Donald Loveland and George Logemann leading to the much more satisfactory DPLL algorithm. After a peripatetic early career that included stints at Bell Labs in the era of Claude Shannon and at the RAND Corporation, Davis settled at New York University, where he spent 30 years on the faculty and helped to found the computer science department. He retired from NYU in 1996 and moved to Berkeley, California, where he now resides with his wife Virginia, who is a textile artist. Davis has a strong interest in history, and in 2000 he published a popular book The Universal Computer, which follows a strand in the history of computing from Leibniz to Turing (the book also appeared, in paperback, under the name Engines of Logic). A new updated  edition (with the original title) has been published in connection with the Turing Centenary.