Matiyasevich's theorem, proven in 1970 by Yuri Matiyasevich, implies that Hilbert's tenth problem is unsolvable. This problem is the challenge to find a general algorithm which can decide whether a given system of Diophantine equations (polynomials with integer coefficients) has a solution among the integers. David Hilbert posed the problem in his 1900 address to the International Congress of Mathematicians.
A typical system of diophantine equations looks like this:
- 3x2y − 7y2z3 = 18
- − 7y2 + 8z2 = 0
- ( 3(x1 − x2)2(y1 − y2) − 7(y1 − y2)2(z1 − z2)3 − 18 )2 + ( −7(y1 − y2)2 + 8(z1 − z2)2)2 = 0.
Later work has shown that the question of solvability of a Diophantine equation is undecidable even if the equation only has 9 natural number variables (Matiyasevich, 1977) or 11 integer variables (Zhi Wei Sun, 1992).
Matiyasevich's theorem itself is somewhat more general than the unsolvability of the Tenth Problem. It says:
polynomial with integer coefficients f(n, x1, ..., xk) such that an integer n is in S if and only if there exist some integers x1, ..., xk such that f(n, x1, ..., xk) = 0.
It is not hard to see that every Diophantine set is recursive enumerable: consider a Diophantine equation f(n, x1, ..., xk) = 0. Now we make an algorithm which simply tries all possible values for n, x1, ..., xk and prints n every time f(n, x1, ..., xk) = 0. This algorithm will obviously run forever and will list exactly the n for which f(n, x1, ..., xk) = 0 has a solution in x1, ..., xk.
The conjunction of Matiyasevich's theorem with a result discovered in the 1930s implies that a solution to Hilbert's tenth problem is impossible. The result discovered in the 1930s by several logicians can be stated by saying that some recursively enumerable sets are non-recursive. In this context, a set S of integers is called "recursive" if there is an algorithm that, when given as input an integer n, returns as output a correct yes-or-no answer to the question of whether n is a member of S.
(It is amusing to observe that one of the very few places in modern mathematics where an argument that takes exactly the form of an old-fashioned Aristotelian syllogism is of great interest and is not contemptuously dismissed as uninteresting because trivial. That argument is as follows.
- (Major premise): All recursively enumerable sets are Diophantine.
- (Minor premise): Some recursively enumerable sets are non-recursive.
- (Conclusion): Therefore some Diophantine sets are non-recursive.
One can also derive the following stronger form of Gödel's incompleteness theorem from Matiyasevich's result:
- Corresponding to any given axiomatization of number theory, one can explicitly construct a Diophantine equation which has no solutions, but such that this fact cannot be proved within the given axiomatization.
- Y. Matiyasevich. "Enumerable sets are Diophantine." Doklady Akademii Nauk SSSR, 191, pp. 279-282, 1970. English translation in Soviet Mathematics. Doklady, vol. 11, no. 2, 1970.
- M. Davis. "Hilbert's Tenth Problem is Unsolvable." American Mathematical Monthly 80, pp. 233-269, 1973.