Martin David Davis (March 8, 1928 – January 1, 2023) was an American mathematician and

computer scientist A computer scientist is a scientist who specializes in the academic study of computer science. Computer scientists typically work on the theoretical side of computation. Although computer scientists can also focus their work and research on ...

who contributed to the fields of

computability theory Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since ex ...

and

mathematical logic Mathematical logic is the study of Logic#Formal logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory (also known as computability theory). Research in mathematical logic com ...

. His work on Hilbert's tenth problem led 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 won the Leroy P. Steele Prize, the Chauvenet Prize (with Reuben Hersh), and the Lester R. Ford Award. He was a fellow of the

American Academy of Arts and Sciences The American Academy of Arts and Sciences (The Academy) is one of the oldest learned societies in the United States. It was founded in 1780 during the American Revolution by John Adams, John Hancock, James Bowdoin, Andrew Oliver, and other ...

and a fellow of the

American Mathematical Society The American Mathematical Society (AMS) is an association of professional mathematicians dedicated to the interests of mathematical research and scholarship, and serves the national and international community through its publications, meetings, ...

Early life and education

Davis's parents were Jewish immigrants to the United States from

Łódź Łódź is a city in central Poland and a former industrial centre. It is the capital of Łódź Voivodeship, and is located south-west of Warsaw. Łódź has a population of 655,279, making it the country's List of cities and towns in Polan ...

, 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 The Bronx ( ) is the northernmost of the five Boroughs of New York City, boroughs of New York City, coextensive with Bronx County, in the U.S. state of New York (state), New York. It shares a land border with Westchester County, New York, West ...

, where his parents encouraged him to obtain a full education.. He graduated from the prestigious Bronx High School of Science in 1944 and went on to receive his bachelor's degree in mathematics from City College in 1948 and his PhD from

Princeton University Princeton University is a private university, private Ivy League research university in Princeton, New Jersey, United States. Founded in 1746 in Elizabeth, New Jersey, Elizabeth as the College of New Jersey, Princeton is the List of Colonial ...

in 1950. His doctoral dissertation, entitled ''On the Theory of Recursive Unsolvability'', was supervised by American mathematician and computer scientist

Alonzo Church Alonzo Church (June 14, 1903 – August 11, 1995) was an American computer scientist, mathematician, logician, and philosopher who made major contributions to mathematical logic and the foundations of theoretical computer science. He is bes ...

Academic career

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 Nokia Bell Labs, commonly referred to as ''Bell Labs'', is an American industrial research and development company owned by Finnish technology company Nokia. With headquarters located in Murray Hill, New Jersey, Murray Hill, New Jersey, the compa ...

and the

RAND Corporation The RAND Corporation, doing business as RAND, is an American nonprofit global policy think tank, research institute, and public sector consulting firm. RAND engages in research and development (R&D) in several fields and industries. Since the ...

before joining

New York University New York University (NYU) is a private university, private research university in New York City, New York, United States. Chartered in 1831 by the New York State Legislature, NYU was founded in 1832 by Albert Gallatin as a Nondenominational ...

. 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 The University of California, Berkeley (UC Berkeley, Berkeley, Cal, or California), is a Public university, public Land-grant university, land-grant research university in Berkeley, California, United States. Founded in 1868 and named after t ...

Hilbert's tenth problem

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 David Hilbert (; ; 23 January 1862 – 14 February 1943) was a German mathematician and philosopher of mathematics and one of the most influential mathematicians of his time. Hilbert discovered and developed a broad range of fundamental idea ...

, asks a question: given a

Diophantine equation ''Diophantine'' means pertaining to the ancient Greek mathematician Diophantus. A number of concepts bear this name: *Diophantine approximation In number theory, the study of Diophantine approximation deals with the approximation of real n ...

, 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 Hilary Whitehall Putnam (; July 31, 1926 – March 13, 2016) was an American philosopher, mathematician, computer scientist, and figure in analytic philosophy in the second half of the 20th century. He contributed to the studies of philosophy of ...

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".

Other contributions

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 In computer science, a search algorithm is an algorithm designed to solve a search problem. Search algorithms work to retrieve information stored within particular data structure, or calculated in the Feasible region, search space of a problem do ...

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. In addition to his work on

, Davis also made significant contributions to the fields of computational complexity and

. Davis was also known for his model of Post–Turing machines. 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 A fellow is a title and form of address for distinguished, learned, or skilled individuals in academia, medicine, research, and industry. The exact meaning of the term differs in each field. In learned society, learned or professional society, p ...

of the

in 1982, and in 2013, he was selected as one of the inaugural fellows of the

. Davis's 1958 book ''Computability and Unsolvability'' is considered a classic in

theoretical computer science Theoretical computer science is a subfield of computer science and mathematics that focuses on the Abstraction, abstract and mathematical foundations of computation. It is difficult to circumscribe the theoretical areas precisely. The Associati ...

, while his 2000 book ''The Universal Computer'' traces the evolution and history of computing starting including works of

Gottfried Wilhelm Leibniz Gottfried Wilhelm Leibniz (or Leibnitz; – 14 November 1716) was a German polymath active as a mathematician, philosopher, scientist and diplomat who is credited, alongside Sir Isaac Newton, with the creation of calculus in addition to ...

and

Alan Turing Alan Mathison Turing (; 23 June 1912 – 7 June 1954) was an English mathematician, computer scientist, logician, cryptanalyst, philosopher and theoretical biologist. He was highly influential in the development of theoretical computer ...

. His book ''The Undecidable'', the first edition of which was published in 1965, was a collection of unsolvable problems and

computable function Computable functions are the basic objects of study in computability theory. Informally, a function is ''computable'' if there is an algorithm that computes the value of the function for every value of its argument. Because of the lack of a precis ...

Personal life and death

Davis was married to Virginia Whiteford Palmer, a textile artist. The couple met during their time in the Urbana–Champaign area and subsequently married in 1951. They had two children. The couple lived in

Berkeley, California Berkeley ( ) is a city on the eastern shore of San Francisco Bay in northern Alameda County, California, United States. It is named after the 18th-century Anglo-Irish bishop and philosopher George Berkeley. It borders the cities of Oakland, Cali ...

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

Selected publications

Books *
Dover reprint
*
2014 Dover reprint
* * Reprinted as * Articles * Davis, Martin (1973)
"Hilbert's Tenth Problem is Unsolvable"
'' The American Mathematical Monthly'', 80(3), 233–269. . * Davis, Martin (1995)
"Is Mathematical Insight Algorithmic?"
'' Behavioral and Brain Sciences'', 13(4), 659–60. * Davis, Martin (2020)
"Seventy Years of Computer Science"
In: Blass A., Cégielski P., Dershowitz N., Droste M., Finkbeiner B. (eds.) ''Fields of Logic and Computation III'', 105–117. Lecture Notes in Computer Science, vol. 12180. Springer: Cham, Switzerland. .

References

External links

*
Celebrating Emil Post & His "Intractable Problem" of Tag: 100 Years Later
on YouTube, including contributions by Martin Davis (from 1 hour 39 minutes in the recording) * * {{DEFAULTSORT:Davis, Martin 1928 births 2023 deaths 20th-century American Jews 20th-century American mathematicians 21st-century American Jews 21st-century American mathematicians American logicians American people of Polish-Jewish descent Courant Institute of Mathematical Sciences faculty Fellows of the American Academy of Arts and Sciences Fellows of the American Mathematical Society Institute for Advanced Study visiting scholars New York University faculty American number theorists Princeton University alumni Scientists from the Bronx