Martin David Davis (March 8, 1928 – January 1, 2023) was a renowned American mathematician and computer scientist who made remarkable contributions to the fields of computability theory and mathematical logic. His work left an indelible mark on the world of mathematics and computer science.
Early Life and Education
Martin David Davis was born in the vibrant city of New York City on March 8, 1928. His parents were Jewish immigrants from Łódź, Poland, who married in New York City after reconnecting. Growing up in the Bronx, his parents instilled in him a strong appreciation for education. He heeded their advice and pursued a comprehensive education.
In 1948, Davis earned his bachelor’s degree in mathematics from City College. His insatiable thirst for knowledge led him to pursue a Ph.D. in Science, which he obtained from the prestigious Princeton University in 1950. His doctoral dissertation, titled “On the Theory of Recursive Unsolvability,” was supervised by the eminent American mathematician and computer scientist, Alonzo Church.
Academic Career
Martin David Davis embarked on a remarkable academic career that took him to various institutions of learning. In the early 1950s, he served as a research instructor at the University of Illinois at Urbana-Champaign. During this period, he became one of the early programmers of the ORDVAC computer. Subsequently, he worked at renowned institutions such as Bell Labs and the RAND Corporation. Later in his career, he played a pivotal role in establishing the computer science department at New York University (NYU). His commitment to academia continued, and he retired from NYU in 1996. Additionally, he contributed to the field of computer science as a visiting faculty member at the University of California, Berkeley.
Contributions to Mathematics and Computer Science
Hilbert’s Tenth Problem
One of Martin David Davis’s most notable achievements was his groundbreaking work on Hilbert’s tenth problem. This problem, posed by the German mathematician David Hilbert, revolved around determining whether a Diophantine equation had an algorithmic solution. Davis’s early engagement with this problem during his Ph.D. dissertation led to a conjecture that it was unsolvable. Collaborating with American mathematicians Hilary Putnam and Julia Robinson in the 1950s and 1960s, they made significant progress toward solving this conjecture. The culmination of their efforts came in 1970 with the contribution of Russian mathematician Yuri Matiyasevich, resulting in the MRDP theorem—named after Martin David Davis, Hilary Putnam, Julia Robinson, and Yuri Matiyasevich. Davis had described this problem as “irresistibly seductive” and a “lifelong obsession.”
The DPLL Algorithm
In 1961, Martin David Davis collaborated with Hilary Putnam, George Logemann, and Donald W. Loveland to develop the Davis–Putnam–Logemann–Loveland (DPLL) algorithm. This backtracking-based search algorithm proved to be instrumental in solving propositional logic formulae in conjunctive normal form (CNF-SAT), an essential component of Boolean satisfiability solvers. This algorithm built upon their earlier work, the Davis–Putnam algorithm, which was established in 1960. The DPLL algorithm remains foundational in the architecture of fast Boolean satisfiability solvers.
Other Contributions
Beyond his work on computability theory, Martin David Davis made significant contributions to computational complexity and mathematical logic. He also introduced his model of Post–Turing machines, further enriching the field of computer science.
Honors and Awards
Martin David Davis received numerous honors and awards in recognition of his outstanding contributions. Notably, he was awarded the Leroy P. Steele Prize, the Chauvenet Prize (shared with Reuben Hersh), and the Lester R. Ford Award. He was honored as a fellow of both the American Academy of Arts and Sciences and the American Mathematical Society.
Published Works
Martin David Davis’s impact extended to the world of literature, with his books becoming pivotal resources in theoretical computer science. His 1958 book, “Computability and Unsolvability,” is considered a classic in the field. In 2000, he penned “The Universal Computer,” tracing the evolution and history of computing, including the works of luminaries such as Gottfried Wilhelm Leibniz and Alan Turing. His book “The Undecidable,” first published in 1965, offered a collection of unsolvable problems and computable functions, adding to his legacy in mathematical literature.
Personal Life and Legacy
In his personal life, Martin David Davis was married to Virginia Whiteford Palmer, a talented textile artist. The couple’s union began in 1951 after they met during their time in the Urbana–Champaign area. They were blessed with two children and shared their life together in Berkeley, California, following Davis’s retirement.
Passing
Tragically, Martin David Davis passed away on January 1, 2023, at the age of 94. Remarkably, his wife, Virginia Whiteford Palmer, also passed away on the same day, just several hours later. Martin David Davis’s legacy endures through his groundbreaking work in mathematics and computer science, and his influence will continue to inspire generations of scholars and researchers in these fields.
