Martin David Davis

Born: 8 March 1928 in New York City, New York, USA

Martin Davis's parents, Helen Gotlieb and Harry Davis, were brought up in Łódź, Poland. Both were Jewish and had known each other in Łódź before emigrating to the United States. Martin Davis wrote [1]:-
My mother as a teenage girl frequented the lending library that my father with other young 'free-thinkers' had set up.
They met again in New York after emigrating and they were married in that city. Martin was the oldest of his parents' two children, having a younger brother Jerome born in 1933. Sadly Jerome died of a ruptured appendix at the age of eight, a devastating blow for thirteen year old Martin and his parents. Harry and Helen Davis had no formal education but learnt English at a night school for immigrants after arriving in New York. Harry was a talented artist but worked hard to support his family as an embroiderer of ladies clothes and household linen. Helen made women's corsets which she sold from a downstairs room in their apartment. The family struggled during the Depression and turned to the Home Relief programme during the middle 1930s to have sufficient food to live. The young Davis was educated in public schools in New York, gaining much from the excellent Bronx High School of Science. This school had been founded in 1938, not long before Davis began his education there [7]:-
I was a bookish boy. And I got beat up a lot by more athletic boys! I got interested in science quite early. I wanted to be a paleontologist, then I wanted to be a physicist, and finally I fell in love with mathematics.
He graduated from the High School in 1944 and entered the City College of New York later that same year [7]:-
... at City College, there were two people who had a big influence on me. One was Emil L Post, who was a great logician and a very direct influence on the direction of my work, and Bennington Gill, who was really a very inspiring teacher, even though his mathematical productivity pretty much ended with his dissertation.
Davis took a course on symbolic mathematical logic in his first year and a reading course on real variable theory with Emil Post in his second year. In his third year he began taking a reading course with Post on mathematical logic but this stopped when Post had a breakdown. Certainly by the time Davis graduated from the City College with a B.S. in 1948 he knew he wanted to undertake research in mathematical logic. He had already written a report as part of an advanced logic course he had taken in his final year and this was later incorporated into his Ph.D. thesis. After graduating, he entered Princeton to undertake research with Alonso Church as his advisor.

As a graduate student at Princeton, Davis was unhappy. He spoke in [7] about a "very heavy culture clash" which made Princeton a difficult environment for a boy from a working class Jewish family brought up in the Bronx. He studied there for only two years, being awarded a Master's degree in 1949 and a Ph.D. in May 1950. Although he had become fascinated by Hilbert's Tenth Problem while studying with Post at the City College, he deliberately chose to concentrate on other topics for his thesis, namely hyperarithmetic hierarchy. His thesis On the Theory of Recursive Unsolvability did, however, contain a chapter on Hilbert's Tenth Problem where he introduced the important idea of the Davis normal form. Since it played such a major role in Davis's career, perhaps we should say a little more about Hilbert's Tenth Problem at this stage. The problem, as stated by David Hilbert at the International Congress of Mathematicians in Paris in 1900, is rather different from the way that it is usually stated today so let us look at both aspects. The original problem is:

Devise a process according to which it can be determined by a finite number of operations whether a given polynomial equation with integer coefficients in any number of unknowns is solvable in rational integers.
The more modern statement would be:
Does there exist an algorithm to determine whether a Diophantine equation has a solution in natural numbers?
The differences in these two statements are significant. Hilbert believed that an algorithm (i.e. a process determined by a finite number of operations) existed and the problem was to find it. However, certainly Post believed that the problem "begs for an unsolvability proof" and had used these words in his discussions with Davis. Let us now return to discussing Davis's career after the award of his doctorate.

In 1950 he was appointed as a research instructor at the University of Illinois at Urbana-Champaign. There he taught a logic course which had computability as one of the main topics. This part of the course formed the basis for his book Computability and Unsolvability which was published in 1958. It is interesting to quote from Davis's Preface:-

This book is an introduction to the theory of computability and noncomputability, usually referred to as the theory of recursive functions. This subject is concerned with the existence of purely mechanical procedures for solving problems. Although the theory is a branch of pure mathematics, it is, because of its relevance to certain philosophical questions and to the theory of digital computers, of potential interest to nonmathematicians. The existence of absolutely unsolvable problems and the Gödel incompleteness theorem are among the results in the theory of computability which have philosophical significance. The existence of universal Turing machines, another result of the theory, confirms the belief of those working with digital computers that it is possible to construct a single 'all-purpose' digital computer on which can be programmed (subject of course to limitations of time and memory capacity) any problem that could be programmed for any conceivable deterministic digital computer. This assertion is sometimes heard in the strengthened form: anything that can be made completely precise can be programmed for an all-purpose digital computer. However, in this form, the assertion is false. In fact, one of the basic results of the theory of computability (namely, the existence of nonrecursively enumerable sets) may be interpreted as asserting the possibility of programming a given computer in such a way that it is impossible to program a computer (either a copy of the given computer or another machine) so as to determine whether or not a given item will be a part of the output of the given computer. Another result (the unsolvability of the halting problem) may be interpreted as implying the impossibility of constructing a program for determining whether or not an arbitrary given program is free of 'loops.'
It was at Urbana-Champaign that Davis met Virginia Whiteford Palmer whom he married on 21 September 1951. Virginia had an A.B. from Smith College, awarded in 1950, and studied Library Science at the University of Illinois. Virginia, who became a textile artist, and Martin Davis had two children, Harold and Nathan. Davis was two years at Urbana-Champaign then spent the two years 1952-54 at the Institute for Advanced Study at Princeton. In 1954 he was appointed as an Assistant Professor of Mathematics at the University of California at Davis where he spent a year before accepting a similar position at Ohio State University. Again after a year, he moved to the Hartford Graduate Division of the Rensselaer Polytechnic Institute in Troy, New York in 1956. His first position at Rensselaer was as Assistant Professor of Mathematics but he was soon promoted to Associate Professor and remained there until 1959. He then spent the year 1959-60 as a Research Scientist and Associate Professor of Mathematics at New York University, following which he spent the years 1960-65 at Yeshiva University, a Jewish university in New York.

During these years when Davis was moving around spending time at various institutions, he published a number of important papers such as Arithmetical problems and recursively enumerable predicates (1953), The definition of universal Turing machine (1957), (with Hilary Putnam) Reductions of Hilbert's tenth problem (1958) and (with Hilary Putnam and Julia Robinson) The decision problem for exponential diophantine equations (1961). In the first of these papers Davis made a very significant hypothesis relating to Hilbert's Tenth Problem:

Diophantine sets are precisely those that can be generated by recursive functions or, what is the same thing, by a Turing machine.
The 1958 paper with Hilary Putnam was the result of their families sharing a house while at a five-week logic conference at Cornell in the summer of 1957. They then met up during the summers of the following three years, doing their most significant work on Hilbert's Tenth Problem in 1959. It would not be Davis who would eventually solve the Tenth Problem, rather it was solved in 1970 by Yuri Matiyasevich following further progress by Julia Robinson.

For his work on Hilbert's Tenth Problem, particularly his remarkable paper explaining the proof, Davis received many honours and awards. In January 1975 he was awarded the Leroy P Steele Prize by the American Mathematical Society:-

... for his paper "Hilbert's tenth problem is unsolvable" (1973).
It was this paper which also gained him the Chauvenet Prize of the Mathematical Association of America in January 1975. In the same month he was awarded the Lester R Ford Prize from the Mathematical Association of America. He was the Mathematical Association of America's Earle Raymond Hedrick Lecturer in 1976. In 1982 he was elected to the American Academy of Arts and Sciences and was awarded a Guggenheim Foundation Fellowship in 1983-84. In 2001 he was awarded a Townsend Harris Medal by the Alumni Association of the City College of New York.

Finally let us look at some of the highly significant books that Davis has published. We have already mentioned Computability and unsolvability (1958) and quoted from the Preface. However, let us now give an indication of its reception by reviewers. C Elgot writes [4]:-

The author succeeds admirably in presenting a readable, motivated, yet not verbose, exposition of the theory of recursive functions.
Clifford Spector writes [12]:-
This text in recursive function theory is written for a wide audience. The first half could be used for advanced undergraduates, and the book as a whole provides a compact yet comprehensive introduction to the subject suitable for a graduate course. In addition it may be of interest to non-mathematicians such as philosophers and engineers. Aside from the ability to follow detailed proofs, very little mathematical background is required of the reader. The inclusion of intuitive explanations at crucial points makes it possible to skip many of the proofs if desired, or can serve to help the uninitiated student to develop the ability to follow rigorous proofs. On the other hand, recent developments are presented in a form for the more mature readers. One very desirable feature is the inclusion of convincing arguments that the fundamental definitions are natural rather than arbitrary.
Louis Kattsoff seems less certain that the level is that broad [8]:-
Although it is good to have this book, it is not precisely an "introduction" in the sense that students are led into the field "from scratch."
We noted above that Computability and unsolvability started life as a lecture course while Davis's books Lecture notes on mathematical logic (1959) and Computability (1974) are actually lecture courses. The second of these consists of notes of lectures given during 1973-1974 at Courant Institute of Mathematical Sciences at New York University. Another interesting book by Davis is Applied nonstandard analysis (1977). The nature of this book is set by Davis's first sentence:-
Nonstandard analysis is a technique rather than a subject.
Davis republished Computability and unsolvability in 1982 but added his 1973 award winning paper Hilbert's tenth problem is unsolvable (1973) as an appendix. Michael Stob [13] criticises the book for being 25 years old, and therefore out of date, but says that it is worth buying for the appendix which:-
... is a completely self-contained exposition of the proof that there is no algorithm for determining whether an arbitrary Diophantine polynomial equation with integer coefficients has an integer solution. It is a masterfully written article and, given to an undergraduate, is sure to awaken interest in computability theory. I know, I read it as an undergraduate and have been in love with recursion theory every since.
In 1983 Davis, in collaboration with Elaine J Weyuker, published Computability, complexity, and languages. Fundamentals of theoretical computer science. The authors write in the Preface:-
It is our purpose in writing this book to provide an introduction to the various aspects of theoretical computer science that is sufficiently comprehensive that the professional literature of treatises and research papers will become accessible to our readers. It is our hope, however, that this book will help readers to see theoretical computer science not as a fragmented list of discrete topics, but rather as a unified subject drawing on powerful mathematical methods and on intuitions derived from experience to give valuable insights into a vital new area of human knowledge.
John Helm, reviewing the book, writes:-
... the reviewer believes that this book fills a real need because of its comprehensiveness and its completeness, and predicts that it will be widely used as a text and reference for some time to come.
In 2000 Davis published The universal computer. The road from Leibniz to Turing which was reprinted in the following year under the title Engines of logic. Mathematicians and the origin of the computer:-
This is an important book: it describes, for a wide audience, the logical underpinnings of computers and thus supplements in an illuminating way the remarkable story of the technological advances that make modern computers possible.
John Dawson, reviewing the book, writes [2]:-
This book surveys developments in mathematics and logic that led the way to the design and construction of modern digital computers. ... its focus is on conceptual rather than technological advances.
Davis retired from his chair in New York University in 1996 and moved to Berkeley, in California.

Article by: J J O'Connor and E F Robertson

July 2011
MacTutor History of Mathematics