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.

URL of the original Home page of the book is http://logic.pdmi.ras.ru/~yumat/H10Pbook.

It has a mirror at http://www.informatik.uni-stuttgart.de/ifi/ti/personen/Matiyasevich/H10Pbook.

All comments can be e-mailed to the author of the book.