Matiyasevichs theorem

Hilbert's tenth 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. This was proven to be impossible by Yuri Matiyasevich in 1970; his result is known as Matiyasevich's theorem.

David Hilbert posed the problem in his 1900 address to the International Congress of Mathematicians.

A typical system of diophantine equations looks like this:

3x²y - 7y²z³ = 18

-7y² + 8z² = 0

The question is whether there exist integers x, y and z which satisfy both equations simultaneously. It turns out that it is equivalent to ask for an algorithm which takes as input a single Diophantine equation with several variables and decides whether that equation 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(x₁ - x₂)²(y₁ - y₂) - 7(y₁ - y₂)²(z₁ - z₂)³ - 18 )² + ( -7(y₁ - y₂)² + 8(z₁ - z₂)²)² = 0.

Building on earlier work by Julia Robinson, Martin Davis and Hilary Putnam, Matiyasevich was able to prove the impossibility of this task by utilizing an ingenious trick involving Fibonacci numbers in order to show that solutions to Diophantine equations may grow exponentially. Later work has shown that the question of solvability of a Diophantine equation is undecidable even if the number of variables is only 6.

Matiyasevich's theorem has since been used to prove that many problems from calculus and differential equations are unsolvable.

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 there is a Diophantine equation which has no solutions, but such that this fact cannot be proved within the given axiomatization.

---

References:

• 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.
• M. Davis and R. Hersh. "Hilbert's 10th Problem." Scientific American 229, pp. 84-91, Nov. 1973.