Hilbert's tenth problem
Hilbert's tenth problem is the tenth on the list of Hilbert's problems of 1900. Its statement is as follows:
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 in a finite number of operations whether the equation is solvable in rational integers.
From the perspective of the theory of computation, Hilbert's 10th problem is concerned with the membership problem for the solutions of a Diophantine equation. The Matiyasevich/MDRP theorem has shown that recursively enumerable sets are equivalent to Diophantine sets. This provides a negative answer to Hilbert's 10th problem because it shows that it is a semi-decidable problem, which is a type of undecidable problem.
The answer to this problem is the combined work of Martin Davis, Yuri Matiyasevich, Hilary Putnam and Julia Robinson which spans 21 years, with Yuri Matiyasevich completing the theorem in 1970.
The words "process" and "finite number of operations" have been taken to mean that Hilbert was asking for an algorithm. The term "rational integer" simply refers to the integers, positive, negative or zero: 0, ±1, ±2, ... . So Hilbert was asking for a general algorithm to decide whether a given polynomial Diophantine equation with integer coefficients has a solution in integers.
Such an equation can be put in the form
where p is a polynomial with integer coefficients, the ai are the unknowns that form the solution and the xj the parameters. The polynomial has both unknowns and parameters because it refers to the general form of the diophantine equation. In the case of the linear diophantine equation
solving the equation consists in finding the solutions a1, a2 for given x1, x2, x3.
Hilbert's problem is not concerned with finding the solutions. It only asks whether one or more solutions exist. The answer to this question is negative, in the sense that no "process can be devised" for answering that question. In modern terms, Hilbert's 10th problem is an undecidable problem. Although it is unlikely that Hilbert had conceived of such a possibility, before going on to list the problems, he did presciently remark:
...
Wikipedia