%%% ====================================================================
%%%  @TeX-file{
%%%     filename        = "preface.tex",
%%%     version         = "1.00",
%%%     date            = "27 October 1993",
%%%     time            = "15:42:41 EDT",
%%%     author          = "Yuri Matijasevich",
%%%     maintaine-by    = "David M. Jones",
%%%     address         = "MIT Laboratory for Computer Science
%%%                        Room NE43-316
%%%                        545 Technology Square
%%%                        Cambridge, MA 02139
%%%                        USA",
%%%     telephone       = "(617) 253-5936",
%%%     FAX             = "(617) 253-3480",
%%%     checksum        = "53872 410 1888 15687",
%%%     email           = "dmjones@theory.lcs.mit.edu",
%%%     codetable       = "ISO/ASCII",
%%%     keywords        = "",
%%%     supported       = "yes",
%%%     docstring       = "This is the preface to {\em Hilbert's Tenth
%%%                        Problem\/} by Yuri Matijasevich (MIT Press,
%%%                        1993).
%%%
%%%                        This file is copyrighted by MIT Press,
%%%                        1993.
%%%
%%%                        This and related files are available via
%%%                        anonymous ftp from theory.lcs.mit.edu in
%%%                        the directory pub/hilbert10.  See the file
%%%                        ``README'' in that directory for a list and
%%%                        description of what is available.
%%%
%%%                        The checksum field above contains a CRC-16
%%%                        checksum as the first value, followed by the
%%%                        equivalent of the standard UNIX wc (word
%%%                        count) utility output of lines, words, and
%%%                        characters.  This is produced by Robert
%%%                        Solovay's checksum utility.",
%%%  }
%%% ====================================================================

\xunnumbered{Preface}

In 1900 _[aut]{Hilbert, David}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:
\begin{quote}

{\raggedright\sc 10. Determination of the solvability
of a Diophantine equation\par}

Given a diophantine equation with any number of unknown quantities and
with rational integral numerical coefficients: {\em 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}.

\end{quote}

Today we read the words ``devise a process'' to mean ``find an
algorithm.'' When _[aut]{Hilbert, David}Hilbert's Problems were posed,
there was no mathematically rigorous {\em general\/} notion of
algorithm available.  The lack of such a notion was not in itself an
obstacle to a positive solution of _[aut]{Hilbert, David}Hilbert's
Tenth Problem, because for any {\em 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\"odel, Alonzo Church, Alan Turing, and other
logicians provided a rigorous formulation of the notion of {\em
computability\/}; this made it possible to establish {\em 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 _[aut]{Hilbert, David}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 _[aut]{Hilbert, David}Hilbert's Tenth Problem
in 1970.

\kludge{\looseness=1}
As in the case of many other problems whose solution was long awaited,
the technique developed for the resolution of _[aut]{Hilbert,
David}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 _[aut]{Hilbert, David}Hilbert's Tenth Problem.
The main technical result implying the unsolvability of
_[aut]{Hilbert, David}Hilbert's Tenth Problem asserts that the class
of {\em Diophantine sets\/} is identical with the class of {\em
recursively enumerable sets}.  Another corollary of this same result
that uses no special terminology states: {\em 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
_[aut]{Hilbert, David}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 _[aut]{Hilbert, David}Hilbert's Tenth Problem
is presented (in varying detail) in many books and surveys, in
particular, in the following publications:
_[aut]{Azra, {Jean-Pierre}}Azra~[1971],
_[aut]{Borger@B{\"o}rger, E.}B\"orger~[1989],
_[aut]{Davis, Martin}Davis~[1973a],
_[aut]{Fenstad, Jens Erik}Fenstad~[1971],
_[aut]{Hermes, Hans}Hermes~[1972, 1978],
_[aut]{Hirose, Ken}Hirose~[1973],
_[aut]{Jones, James P.}Jones and
_[aut]{Matiyasevich, Yu. V.}Matiyasevich~[1991],
_[aut]{Kaplansky, Irving}Kaplansky~[1977],
_[aut]{Manin, {{\Yu}}. I.}Manin~[1973],
_[aut]{Manin, {{\Yu}}. I.}Manin and
_[aut]{Pan{\ch}i{\sh}kin, A. A.}Pan{\ch}i{\sh}kin~[1990],
_[aut]{Margenstern, M.}Margenstern~[1981],
_[aut]{Matiyasevich, Yu. V.}Matiyasevich [1972a],
_[aut]{Mijajlovi{\'c}, {\v{Z}}arko}Mijajlovi{\'c},
_[aut]{Markovi{\'c}, Zoran}Markovi{\'c}, and
_[aut]{Dosen@Do{\v{s}}en, Kosta}Do\v{s}en~[1986],
_[aut]{Ruohonen, Keijo}Ruohonen~[1972, 1980],
_[aut]{Salomaa, Arto}Salomaa [1985],
_[aut]{Smory\'nski, Craig}Smory{\'n}ski~[1991],
_[aut]{Sussman, H{\'e}ctor J.}Sussman~[1971], and
_[aut]{Zakharov, D. A.@Za{{\kh}}arov, D. A.}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 _[aut]{Hilbert, David}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 {\em Appendix}.

Each chapter is concluded by {\em 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 {\em Hints\/} supply the ideas of the proofs and/or
references to the literature.

In addition to the exercises, there are a few {\em Open Questions\/}
and {\em 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 {\em 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 {\em Bibliography\/} lists all of the principal publications
concerned with the negative solution to _[aut]{Hilbert,
David}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 numbering of formulas in each section begins with~1. To refer to a
%%  formula from another section, we add the section number preceding the
%%  formula number; thus~(5.3) is formula~(3) from Section~5 of the same
%%  chapter.  Similarly, (2.4.6) is formula~(6) from Section~2.4, i.e.,
%%  from Section~4 of Chapter~2.

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 _[aut]{Hilbert, David}Hilbert's Tenth Problem.  Figure~1
exhibits 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.

\begin{figure}
\begin{center}
\begin{tabular}{lllllll}
&&&&&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
\end{tabular}
\end{center}
\caption{}
\end{figure}

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):

\begin{figure}
\begin{center}
\begin{tabular}{llllllll}
2.1& 2.4& 3.4& 5.4& 5.5& 5.7& \bf7.1& \bf7.2 \\
\bf7.3& \bf6.4& \bf6.2&& \bf6.1&
\bf9.1& \bf9.2& \bf9.3 \\
\bf7.4&& \bf6.3&&& \bf10.1& \bf10.2
\end{tabular}
\end{center}
\caption{}
\end{figure}

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.

\endinput

\begin{figure}

\begin{center}

\setlength{\unitlength}{.25in}

\begin{picture}(18,26)
\small
\put(8,26){\circle*{.125}}      % 1.1
\plabel(8,26){1.1}
%\put(8,26){\makebox{1.1}}      % 1.1
\put(8,26){\vector(0,-1){1}}    % 1.1 ==> 1.2

\put(8,25){\circle*{.125}}      % 1.2
\plabel(8,25){1.2}
\put(8,25){\vector(0,-1){1}}    % 1.2 ==> 1.3

\put(8,24){\circle*{.125}}      % 1.3
\plabel(8,24){1.3}
\put(8,24){\vector(0,-1){1}}    % 1.3 ==> 1.4

\put(8,23){\circle*{.125}}      % 1.4
\plabel(8,23){1.4}
\put(8,23){\vector(0,-1){1}}    % 1.4 ==> 1.5

\put(8,22){\circle*{.125}}      % 1.5
\plabel(8,22){1.5}
\put(8,22){\vector(-1,-1){3}}   % 1.5 ==> 1.6
\put(8,22){\vector(1,-1){3}}    % 1.5 ==> 3.1

\put(5,19){\circle*{.125}}      % 1.6
\plabel[r](5,19){1.6}
\put(11,19){\circle*{.125}}     % 3.1
\plabel(11,19){3.1}

\put(5,19){\vector(-1,-1){3}}   % 1.6 ==> 2.1
\put(5,19){\vector(1,-1){3}}    % 1.6 ==> 3.2

\put(2,16){\circle*{.125}}      % 2.1
\plabel[r](2,16){2.1}
\put(8,16){\circle*{.125}}      % 3.2
\plabel(8,16){3.2}

\put(11,19){\vector(-1,-1){3}}  % 3.1 ==> 3.2

\put(2,16){\vector(0,-1){1}}    % 2.1 ==> 2.2
\put(2,15){\circle*{.125}}      % 2.2
\plabel[r](2,15){2.2}

\put(2,15){\vector(0,-1){1}}    % 2.2 ==> 2.3
\put(2,14){\circle*{.125}}      % 2.3
\plabel[r](2,14){2.3}

\put(2,14){\vector(0,-1){1}}    % 2.3 ==> 2.4
\put(2,13){\circle*{.125}}      % 2.4
\plabel[r](2,13){2.4}

\put(2,13){\vector(0,-1){1}}    % 2.4 ==> 2.5
\put(2,12){\circle*{.125}}      % 2.5
\plabel[r](2,12){2.5}

\put(2,12){\vector(1,-1){2}}    % 2.5 ==> 3.3
\put(4,10){\circle*{.125}}      % 3.3
\plabel(4,10){3.3}

\put(8,16){\vector(-2,-3){4}}   % 3.2  ==> 3.3

\put(11,19){\vector(0,-1){3}}   % 3.1 ==> 4.1
\put(11,16){\circle*{.125}}     % 4.1
\plabel(11,16){4.1}

\put(11,16){\vector(0,-1){2}}   % 4.1 ==> 4.2
\put(11,14){\circle*{.125}}     % 4.2
\plabel(11,14){4.2}

\put(4,10){\vector(-1,-1){1}}   % 3.3 ==> 3.4
\put(3,9){\vector(-1,-1){1}}    % 3.4 ==> 3.5
\put(4,10){\vector(1,-1){2}}    % 3.3 ==> 4.3

\put(3,9){\circle*{.125}}       % 3.4
\plabel[r](3,9){3.4}

\put(2,8){\circle*{.125}}       % 3.5
\plabel[r](2,8){3.5}
\put(6,8){\circle*{.125}}       % 4.3
\plabel(6,8){4.3}

\put(11,14){\line(-5,-6){5}}    % 4.2 ==> 4.3

\put(2,8){\vector(1,-1){2}}     % 3.5 ==> 4.4
\put(6,8){\vector(-1,-1){2}}    % 4.3 ==> 4.4

\put(4,6){\circle*{.125}}       % 4.4
\plabel(4,6){4.4}

\put(2,8){\vector(-1,-1){2}}    % 3.5 ==> 3.6
\put(0,6){\circle*{.125}}       % 3.6
\plabel[r](0,6){3.6}

\put(0,6){\vector(0,-1){2}}     % 3.6 ==> 5.5
\put(0,4){\circle*{.125}}       % 5.5
\plabel[r](0,4){5.5}

\put(4,6){\vector(0,-1){1}}     % 4.4 ==> 4.5
\put(4,5){\circle*{.125}}       % 4.5
\plabel(4,5){4.5}

\put(4,5){\vector(0,-1){1}}     % 4.5 ==> 4.6
\put(4,4){\circle*{.125}}       % 4.6
\plabel(4,4){4.6}

\put(0,4){\vector(1,-1){2}}     % 5.5 ==> 5.6
\put(4,4){\vector(-1,-1){2}}    % 4.6 ==> 5.6

\put(2,2){\circle*{.125}}       % 5.6
\plabel[r](2,2){5.6}

\put(2,2){\vector(0,-1){1}}       % 5.6 ==> 5.7
\plabel(2,1){5.7}

\put(14,20){\circle*{.125}}     % 5.1
\plabel(14,20){5.1}
\put(14,20){\vector(0,-1){2}}   % 5.1 ==> 5.2

\put(14,18){\circle*{.125}}     % 5.2
\plabel(14,18){5.2}
\put(14,18){\vector(0,-1){2}}   % 5.1 ==> 5.3

\put(11,19){\vector(1,-1){3}}   % 3.1 ==> 5.3
\put(14,16){\circle*{.125}}     % 5.3
\plabel(14,16){5.3}

\put(14,16){\vector(0,-1){4}}   % 5.3 ==> 5.4
\put(14,12){\circle*{.125}}     % 5.4
\plabel(14,12){5.4}

\put(14,12){\line(-1,-1){10}}   % 5.4 ==> 5.7
\put(4,2){\vector(-1,0){2}}

\put(14,16){\line(1,-1){3}}      % 5.3 ==> 5.5
\put(17,13){\line(-1,-1){13}}
\put(4,0){\line(-1,0){4}}
\put(0,0){\vector(0,1){4}}

\end{picture}

\end{center}

\end{figure}
