In 1900 David Hilbert [1900] delivered his famous lecture entitled "Mathematische Probleme" before the Second International Congress of Mathematicians. This paper contains 23 problems, or, more precisely, 23 groups of related problems, that the nineteenth century left for the twentieth century to solve. Problem number ten is about Diophantine equations:
10. Determination of the solvability of a Diophantine equation
Given a diophantine equation with any number of unknown quantities and with rational integral numerical coefficients: To devise a process according to which it can be determined by a finite number of operations whether the equation is solvable in rational integers.
Today we read the words ``devise a process'' to mean ``find an algorithm.'' When Hilbert's Problems were posed, there was no mathematically rigorous general notion of algorithm available. The lack of such a notion was not in itself an obstacle to a positive solution of Hilbert's Tenth Problem, because for any particular algorithm it was always clear that it actually gave the desired general method for solving the corresponding problem.
During the 1930's, Kurt Gödel, Alonzo Church, Alan Turing, and other logicians provided a rigorous formulation of the notion of computability; this made it possible to establish algorithmic unsolvability, i.e., the impossibility of the existence of an algorithm with certain properties. Soon afterwards the first examples of algorithmically unsolvable problems were found, first in mathematical logic itself and then in other branches of mathematics.
Computability theory produced all the necessary tools for tackling the unsolvability of Hilbert's Tenth Problem. The first in a series of papers in this direction appeared at the beginning of the 1950's. The continuing effort culminated in a ``negative solution'' of Hilbert's Tenth Problem in 1970.
As in the case of many other problems whose solution was long awaited, the technique developed for the resolution of Hilbert's Tenth Problem is of independent value because it has other applications. Some of these are rather striking, and taken together, these other applications are perhaps even more important than the solution of Hilbert's Tenth Problem. The main technical result implying the unsolvability of Hilbert's Tenth Problem asserts that the class of Diophantine sets is identical with the class of recursively enumerable sets. Another corollary of this same result that uses no special terminology states: It is possible to exhibit explicitly a polynomial with integer coefficients such that the set of all the positive values it assumes for integer values of its variables is exactly the set of all prime numbers.
The present book is devoted to the algorithmic unsolvability of Hilbert's Tenth Problem and related topics; the numerous partial results that have been obtained in the direction of a positive solution of the Problem are hardly considered.
The negative solution of Hilbert's Tenth Problem is presented (in varying detail) in many books and surveys, in particular, in the following publications: Azra [1971], Börger [1989], Davis [1973a], Fenstad [1971], Hermes [1972, 1978], Hirose [1973], Jones and Matiyasevich [1991], Kaplansky [1977], Manin [1973], Manin and Panchishkin [1990], Margenstern [1981], Matiyasevich [1972a], Mijajlovic, Markovic, and Dosen [1986], Ruohonen [1972, 1980], Salomaa [1985], Smorynski [1991], Sussman [1971], and Zakharov [1970].
A distinguishing feature of this book is that, in addition to presenting the negative solution of the problem, it contains a number of diverse applications of the technique developed for that solution. At present these applications are scattered among various publications, mainly journal articles. During the twenty years that have passed since the problem was "unsolved," many improvements and modifications of the original proof have been suggested. In addition to these, the book contains several new, previously unpublished proofs.
Understanding the negative solution of Hilbert's Tenth Problem naturally requires some knowledge from both number theory and mathematical logic. Wishing to make the book accessible to a broader readership, especially to younger mathematicians, the author has tried to reduce the mathematical prerequisites needed by the reader. In particular, no knowledge of computability theory is presupposed. All the necessary notions are defined in the book, and thus it can serve as an introduction to this fascinating subject (but of course the book cannot be used for its systematic study). A few number-theoretical results that are usually not part of the basic mathematical curriculum are proved in the Appendix.
Each chapter is concluded by Exercises, which contain problems of varying difficulty. While some of them are quite elementary, others amount to small research problems. The aim of the exercises is to present diverse results, but without proofs. Of course, this division (on the one hand, the main content of the book presented with full proofs and, on the other, the results relegated to the exercises) represents a rather subjective judgement by the author. In particular, the exercises contain results requiring special knowledge or having cumbersome proofs as well as results that are, most likely, far from the best possible or that were thought to be of limited interest. The Hints supply the ideas of the proofs and/or references to the literature.
In addition to the exercises, there are a few Open Questions and Unsolved Problems. Again, the division is quite subjective. It may be that an open question has not been settled simply because no one has tackled it seriously, and the answer may turn out to be without significance. On the other hand, the unsolved problems have attracted the attention of many capable researchers, and solving these problems may require decades.
Each chapter is completed by a Commentary providing a historical view of its contents. This seems to be worthwhile because the logical order of presentation used in the book often doesn't coincide with the chronological order in which the results had originally been obtained.
The Bibliography list all of the principal publications concerned with the negative solution to Hilbert's Tenth Problem as well as most of the papers that apply the technique developed for obtaining that solution. The author would be grateful if omissions were called to his attention.
The book need not be read consecutively. It may be said to consist of two parts. The first part, consisting of Chapters 1--5, presents the solution of Hilbert's Tenth Problem. Figure 1 exibits the dependencies among the sections of the first part. To determine which sections should be read before a particular section U.V, locate that section in the figure and imagine vertical and horizontal coordinate axes placed on the page in such a manner that their point of intersection is at the period in U.V. Then, before reading section U.V you will need to read all sections lying in the upper left quadrant including its boundary.
| 5.1 | ||||||
| 5.2 | ||||||
| 1.1 | ||||||
| 1.2 | ||||||
| 1.3 | ||||||
| 1.4 | ||||||
| 1.5 | 3.1 | 5.3 | 5.4 | |||
| 1.6 | 2.1 | |||||
| 2.2 | ||||||
| 2.3 | ||||||
| 2.4 | ||||||
| 2.5 | ||||||
| 3.1 | 3.2 | 3.3 | 3.4 | |||
| 3.5 | 3.6 | 5.5 | ||||
| 4.1 | ||||||
| 4.2 | 4.3 | 4.4 | ||||
| 4.5 | ||||||
| 4.6 | 5.6 | |||||
| 5.7 |
Similarly, Figure 2 shows how the sections of the second part, devoted to applications, depend on the sections from the first part (but not dependencies between sections of the first part and not dependencies between sections of the second part):
| 2.1 | 2.4 | 3.4 | 5.4 | 5.5 | 5.7 | 7.1 | 7.2 |
| 7.3 | 6.4 | 6.2 | 6.1 | 9.1 | 9.2 | 9.3 | |
| 7.4 | 6.3 | 10.1 | 10.2 |
There are few dependencies among the sections of the second part. Sections 6.1--6.3 offer three different techniques for achieving the same aim; it suffices to know any one of them in order to read Sections 6.4--6.6 and 9.1. Similarly, Sections 4.5 and 6.5 present two different constructions of a universal equation, either of which can serve as background for reading Sections 6.6 and 8.1. Section 8.2 presupposes acquaintance with Section 7.2, which in turn presupposes knowledge of Sections 6.2--6.3; Section 9.4 uses results from Section 9.2, and Section 10.1 is based on Section 6.6.
The English translation of the "Preface" to the book is placed on WWW with kind permition of ©The MIT Press.