Martin Davis and Hilbert’s Tenth Problem

Yuri Matiyasevich

Abstract The paper presents the history of the negative solution of Hilbert’s tenth problem, the role played in it by Martin Davis, consequent modifications of the original proof of DPRM-theorem, its improvements and applications, and a new (2010) conjecture of Martin Davis.

Keywords Computability • Hilbert’s Tenth Problem • DPRM-theorem

The Problem

Martin Davis will stay forever in the history of mathematics and computer science as a major contributor to the solution of Hilbert’s tenth problem.

This was one among 23 problems which David Hilbert stated in his famous paper “Mathematical Problems” [18] delivered at the Second International Congress of Mathematicians. This meeting took place in Paris in 1900, on the turn of the century. These problems were, in Hilbert’s opinion, among the most important problems that the passing nineteenth century was leaving open to the pending twentieth century.

The section of [18] devoted to the Tenth Problem is so short that it can be reproduced here in full:

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.

Equations from the statement of the problem have the form

Y. Matiyasevich (B)

Laboratory of Mathematical Logic, St. Petersburg Department of V.A. Steklov Institute of Mathematics (POMI), Russian Academy of Sciences, 27 Fontanka,

St. petersburg, Russia 191023 e-mail: This email address is being protected from spam bots, you need Javascript enabled to view it

© Springer International Publishing Switzerland 2016 35

E.G. Omodeo and A. Policriti (eds.), Martin Davis on Computability,

Computational Logic, and Mathematical Foundations,

Outstanding Contributions to Logic 10, DOI 10.1007/978-3-319-41842-1_2

where P is a polynomial with integer coefficients. The equations are named after the Greek mathematician Diophantus who lived, most likely, in the 3rd century A.D.

The Tenth problem is the only one of the 23 Hilbert’s problems that is (in today’s terminology) a decision problem, i.e., a problem consisting of infinitely many individual problems each of which requires a definite answer: YES or NO. The heart of a decision problem is the requirement to find a single method that will give an answer to any individual subproblem.

Since Diophantus’s time, number-theorists have found solutions for a large amount of Diophantine equations, and also they have established the unsolvability of a lot of other equations. Unfortunately, for different classes of equations, and often even for different individual equations, it was necessary to invent specific methods. In his tenth problem, Hilbert asks for a universal method for deciding the solvability of all Diophantine equations.

A decision problem can be solved in a positive or in a negative sense, that is, either by discovering a required algorithm or by showing that none exists. Hilbert foresaw the possibility of negative solutions to some mathematical problems, in [18] he wrote:

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 preeminent 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.

But in 1900 it was impossible even to state rigourously what would constitute a negative solution of Hilbert’s tenth problem. The general mathematical notion of algorithm was developed by Alonzo Church, Kurt Godel, Alan Turing, Emil Post, and other logicians only three decades after Hilbert’s lecture [18].

The appearance of the general notion of algorithms gave the possibility to establish non-existence of algorithms for particular decision problems, and soon such undecidable problems were actually found. But these results didn’t much impress “pure mathematicians” because the first discovered undecidable problems were from the realm of mathematical logic and the just emerging computer science.

The situation changed in 1947 when two mathematician, Andrei Andreevich Markov [28] in the USSR, and Emil Post [45] in the USA, independently proved that there is no algorithm for so called Thue problem. This problem was posed by Alex Thue [58] in 1914, much before the development of the general notion of an algorithm. Thue asked for a method for deciding, given a finitely presented semi?group and two elements from it, whether the defining relations imply the equality of these two elements or not. Thus Thue problem, known also as word problem for semigroups, became the very first decision problem, born in mathematics proper and proved to be undecidable.

After the success with Thue problem, researchers were inspired to establish the undecidability of other long standing open mathematical problems. In particular, both Markov and Post were interested in Hilbert’s tenth problem. Already in 1944 Post wrote in [44] that Hilbert’s tenth problem “begs for an unsolvability proof”. Post had a student to whom this statement produced great impression and he decided to tackle the problem.

The name of this student was Martin Davis.

 
Source
< Prev   CONTENTS   Source   Next >