Martin Davis on Computability, Computational Logic, and Mathematical Foundations

It is a great service that Universität Bielefeld carries the full text of Hilbert’s famous 1900 ICM Paris Address online, seeing that his prescience was unsurpassed: so many of his Paris Problems have proven definitive for ensuing mathematical research, covering essentially all fields in the discipline. Indeed, many modern areas of mathematical activity came into being as a result of the call to action provided by Hilbert at the Paris Congress. A case in point is his 10th Problem which, in the original German reads as follows:

Eine D i o p h a n t i s c h e Gleichung mit irgend welchen Unbekannten und mit ganzen rationalen Zahlencoefficienten sei vorgelegt: man soll ein Verfahren angeben, nach welchem sich mittelst einer endlichen Anzahl von Operationen entscheiden läßt, ob die Gleichung in ganzen rationalen Zahlen lösbar ist.

In English:

Given a Diophantine equation in arbitrary unknowns with integer coefficients: provide a process whereby to determine in a finite number of steps whether this equation is solvable in integers.

The logician featured in the book under review was one of the main players in the negative solution to this problem: no such decision procedure exists.

I recall well, when I was very young and spent hours in bookstores and libraries browsing through whatever I could find that looked like mathematics, coming across an article about the problem mentioned immediately above and the names Martin Davis, Hilary Putnam, Julia Robinson, and Yuri Matiyasevich. My memory may falter a bit now, about 45 years later, but I believe what had caught my attention was the fact that the article in question dealt with prime generating polynomials — but it was long ago, so I may have some wires crossed. In any event, I do recall being captivated (even given my not-even-a-tyro status) and subsequently gravitated to (a rather large number) of courses in set theory and logic, both throughout my undergraduate days and even into my early graduate school years. Of course, truth be told, I’ve never been anything but a sometime hitch-hiker, but happily it’s been enough to justify my teaching occasional seminars in logic — a propos, I am slated to do another one in a near-future semester.

That said, then, it is welcome indeed to have the book under review on my desk and in my possession, particularly given that it’s something of a Festschrift, sporting all sorts of goodies. Doubtless there are a number of these which will have at least one of two very desirable impacts: articles of great intrinsic interest (while being accessible even to a non-specialist like me), and articles of pedagogical use at a rather early academic level. Here are a number of examples that immediately present themselves: Davis himself contributes “[a] brief autobiography [highlighting] events that have had a significant effect on [his] professional development” (cf. “My Life as a Logician”); none other than Matiyasevich presents “Martin Davis and Hilbert’s Tenth Problem” (This one is nigh-on irresistible to me); Blass and Gurevich hit some currently hot stuff in “On Quantum Computation, Anyons, and Categories”; Perlis makes a philosophically very tantalizing suggestion in “Taking Physical Infinity Seriously”; (the late) Hilary Putnam and Davis himself add contributions to “Pragmatic Platonism”; and the entire enterprise is capped off by “Concluding Comments by Martin.” The book has two appendices of significant historical as well as mathematical significance, both by Putnam and Davis, dealing, respectively, with “Feasible Computational Methods in the Propositional Calculus,” and (yes, indeed) “Research on Hilbert’s Tent Problem.” The latter is advertised as “the Original Paper by M. Davis and H. Putnam.”

To real logicians or even to folks like me, tangential some-time enthusiasts who on a good day might qualify for more than a dilettante status, this is a wonderful book to have. The former, modulo a good sense of history, will devour it with zest; the latter, modulo a good sense of mathematical culture, will read at least some of the articles with pleasure.

Michael Berg is Professor of Mathematics at Loyola Marymount University in Los Angeles, CA.