"HILBERT's TENTH PROBLEM"

Alan Turing introduced the abstract computing devices that are now named for him in his classical paper [1936]. A very similar notion was also introduced by Emil L. Post [1936]. Since that time numerous modifications of the Turing-Post machine have been proposed. The version used in Section 5.1 was chosen as being particularly suitable for simulation by Diophantine equations.

Various authors have proposed other approaches for making the general notion of algorithm precise. (An exposition of the history of computability theory (in Russia the subject is often referred to as the theory of algorithms) can be found in Uspenskii and Semënov [1987].) All of these approaches led to equivalent notions of decidable and semidecidable sets (the latter are more often called "recursively enumerable"). Alonzo Church [1936] was the first to realize that a single and, at first sight, very special definition can be adequate for the fundamental notion of computability. Church's Thesis has many equivalent formulations depending on the choice of a particular kind of abstract computing device, and the formulation from Section 5.7 is sometimes called Turing's Thesis. Kolmogorov and Uspenskii [1958] attempted to give the most general definition of an abstract computing device satisfying the requirement that every step should be elementary, and proved its equivalence to more traditional models of computing devices, in particular to Turing machines.

The first papers aimed at proving the algorithmic unsolvability of Hilbert's Tenth Problem appeared in the early 1950's (see the Commentary to Chapter 1). Even at that time, there was no difficulty in proving that all Diophantine sets are semidecidable (for any standard definition of the latter notion). At this same time Martin Davis [1953] set forth the daring hypothesis that the converse is also true, i.e., that every semidecidable set is Diophantine, and thus that the number-theoretic notion of Diophantine set coincides with the notion of semidecidable set from computability theory.

Davis [1950, 1953] took the first step towards proving his hypothesis; namely, he showed that every semidecidable set of natural numbers can be represented in the form

(1)

Such representations are said to be in Davis normal form.

Examples of sets that are semidecidable but not decidable have been known since the 1930's, and hence Davis's hypothesis implied a negative solution of Hilbert's Tenth Problem. However, efforts to prove the hypothesis encountered difficulties. In this situation, it was natural to seek other approaches that, without proving Davis's hypothesis, would nevertheless provide a negative solution of Hilbert's Tenth Problem.

One possible way to weaken Davis's hypothesis is as follows: In the definition of a family of equations given in Section 1.4, it is required that the function D in (1.4.1) should be a polynomial in all the variables a₁, ..., a_n, x₁, ..., x_m. Instead of this, it would be sufficient to require polynomial dependence on x₁, ...,  x_m only. It would suffice that the dependence on a₁, ...,  a_n be via any algorithm that would provide, for any given values of a₁, ..., a_n, a Diophantine equation in x₁, ..., x_m. It is clear that even under such a weakened restriction on D, a positive solution of Hilbert's Tenth Problem would have implied the decidability of the set represented by (1.4.2).

In particular, one could consider the class of exponential Diophantine equations in which unknowns do not occur in the exponents. Such an approach was proposed by A.I.Mal'tsev [1968], but for reasons that are not entirely clear, although he allowed parameters to occur in the exponents, he did not permit parameters to occur polynomially like the unknowns. Thus, Davis's hypothesis does not formally give a solution to the problem posed by Mal'zev; however, a solution can be easily deduced from it (see Exercise 5.8).

Another weakening of Davis's hypothesis was proposed by S. Yu. Maslov [1967].

Davis's hypothesis was finally proved in 1970, but the chronological order in which the proof was obtained was different from the logical order followed in Chapters 1--5. One of the most crucial steps in the historical development consisted in obtaining an exponential Diophantine representation for an arbitrary semidecidable set. This result was first obtained by Davis and Putnam in a conditional form. Their result was announced in an abstract [1959a] and presented with full details in a report [1959b] that is not readily available.

In their proof Davis and Putnam used the still-unproved (1992) conjecture that there exist arbitrarily long arithmetical progressions consisting entirely of prime numbers. It was Julia Robinson who managed to eliminate the conjecture. The new result was announced in her short communication [1960] and a lecture [1962] and then published in the now-classic paper by Davis, Putnam, and Robinson [1961]. In that paper, an exponential Diophantine representation was obtained by eliminating the bounded universal quantifier from the Davis normal form (1). This technique will be presented in Chapter 6.

After it was established that every semidecidable set has an exponential Diophantine representation, it was sufficient to show that exponentiation was Diophantine in order to prove Davis's hypothesis. The history of that stage was presented in the Commentary to Chapter 2.

The proof that exponentiation was Diophantine was not only the final link in the proof of Davis's hypothesis, it also opened new routes for the construction of Diophantine representations of semidecidable sets. In particular, the Davis representation (1) ceased being a necessary step. Earlier it had been necessary because the method used for elimination of the bounded universal quantifier preceding the Diophantine equation in (1) led to an exponential Diophantine equation, and thus the process could not be iterated. Now that we can transform exponential Diophantine equations into Diophantine equations, we can begin with an arithmetic representation of a semidecidable set containing arbitrarily many universal quantifiers. A technique for obtaining arithmetical representations had been found long before by Kurt Gödel [1931].

On the other hand, the fact that exponentiation was Diophantine also made it possible to construct Diophantine representations without any use of bounded universal quantifiers, as was in fact done in Chapters 1--5. An approach of this kind was implemented for the first time by Matiyasevich [1976]. This construction was based on Turing machines, and the main difficulties were connected with the necessity of coding strings of symbols and sequences of their transformations by numbers. In Jones and Matiyasevich [1983, 1984, 1991] and Matiyasevich [1984], another construction is presented in which the initial representation of a semidecidable set is based on register machines (see Exercise 5.7). This model of abstract computing devices was proposed in Lambek [1961], Melzak [1961], Minsky [1961, 1967], and Shepherdson and Sturgis [1963]. Register machines are particularly suitable for constructing Diophantine representations. Like Turing machines, they have very primitive instructions and, in addition, they deal directly with numbers.

The method of Diophantine simulation of Turing machines described in Section 5.5 is different from the method given in Matiyasevich [1976] and is presented here for the first time. For yet another proof via Turing machines, see van Emde Boas [1983].

We conclude with a quotation from Hilbert's lecture  [1900] that reveals his attitude to "negative" results:

Occasionally it happens that we seek the solution under insufficient hypotheses or in an incorrect sense, and for this reason do not succeed. The problem then arises: to show the impossibility of the solution under the given hypotheses, or in the sense contemplated. Such proofs of impossibility were effected by the ancients, for instance when they showed that the ratio of the hypotenuse to the side of an isosceles triangle is irrational. In later mathematics, the question as to the impossibility of certain solutions plays a preëminent part, and we perceive in this way that old and difficult problems, such as the proof of the axiom of parallels, the squaring of circle, or the solution of equations of the fifth degree by radicals have finally found fully satisfactory and rigorous solutions, although in another sense than that originally intended. It is probably this important fact along with other philosophical reasons that gives rise to conviction (which every mathematician shares, but which no one has as yet supported by a proof) that every definite mathematical problem must necessary be susceptible of an exact settlement, either in the form of an actual answer to the question asked, or by the proof of the impossibility of its solution and therewith the necessary failure of all attempts.