The Matiyasevich's theorem reference article from the English Wikipedia on 24-Jul-2004
(provided by Fixed Reference: snapshots of Wikipedia from

Matiyasevich's theorem

Get the latest news from Africa

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
The question is whether there exist integers x, y and z which satisfy both equations simultaneously. It turns out that it is always equivalent to ask whether a single Diophantine equation with several variables has any solutions among the natural numbers. For instance, the above system is solvable over the integers if and only if the following equation is solvable over the natural numbers:
( 3(x1x2)2(y1y2) − 7(y1y2)2(z1z2)3 − 18 )2 + ( −7(y1y2)2 + 8(z1z2)2)2 = 0.

Matiyasevich utilized an ingenious trick involving Fibonacci numbers in order to show that solutions to Diophantine equations may grow exponentially. Earlier work by Julia Robinson, Martin Davis and Hilary Putnam had shown that this suffices to show that no general algorithm deciding the solvability of Diophantine equations can exist.


Matiyasevich's theorem itself is somewhat more general than the unsolvability of the Tenth Problem. It says:

Every recursively enumerable set is Diophantine.


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.


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

The conclusion of this syllogism is what entails that Hilbert's 10th problem cannot be solved.)


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.