The theorem of Youri Matiiassevitch, shown in 1970 by Youri Matiiassevitch, implies that the tenth problem of Hilbert does not have a solution. This problem, which proposed to find an algorithm general to decide if a system of equations diophantiennes (polynomials with whole coefficients) has a solution of integers, was posed by David Hilbert at the time of his conference of 1900 with the international Congrès of mathematics of Paris.

An example of system of equations diophantiennes is the following:

3 X ² there − 7 there ² Z ³ = 18

− 7 there ² + 8 Z ² = 0

The question which arises states as follows: do there exist integers X , there and Z which satisfies simultaneously the two equations? This question is equivalent to that to know if a single equation diophantienne with several variables admits a solution in the natural entireties. For example, the system above has a whole solution if and only if the following equation has a solution in the natural entireties:

(3 ( X ₁ − X ₂) ² ( there ₁ − there ₂) − 7 ( there ₁ − there ₂) ² ( Z ₁ − Z ₂) ³ − 18) ² + (−7 ( there ₁ − there ₂) ² + 8 ( Z ₁ − Z ₂) ²) ² = 0.

Youri Matiiassevitch used an easy way implying the numbers of Fibonacci in order to show that the solutions of the equations diophantiennes can develop exponentially. The first work on this subject is due to Julia Robinson, Martin Davis and Hilary Putnam; they had shown that it is enough to show this result which there does not exist any general algorithm deciding the existence of solutions for the equations diophantiennes.

Posterior work showed that the question of the existence of solutions of an equation diophantienne is indécidable even if the equation has only 9 original variables (Matiyasevich, 1977) or 11 integer variables (Zhi Wei Sun, 1992).

The theorem of Matiiassevitch itself is much stronger than the insolubility of the tenth problem. He affirms that:

a unit is Récursivement énumérable if and only if it is diophantien.

A unit S of integers is recursively énumérable if and only if there is an algorithm which behaves as follows: one gives like entry to the algorithm an integer N, if N belongs to S, then the algorithm stops early or late; if not it is carried out indefinitely. In other words, there exists an algorithm which is carried out indefinitely and produced all the members of S. In addition, a unit S is Diophantien so by definition there exists a Polynôme with whole coefficients P such as N belongs to S if and only if P (N, x1,…, xk) = 0.

It is not difficult to see that each diophantien unit is recursively énumérable. For that let us consider an equation diophantienne F (N, x1,…, xk) = 0 and imagine an algorithm which traverses all the possible values for N, x1,…, xk, in the order ascending of the sum of their absolute values, and turns over N each time F (N, x1,…, xk) = 0. Obviously this algorithm will be carried out without end and will enumerate N for which F (N, x1,…, xk) = 0 has a solution.

The conjunction of the theorem of Youri Matiiassevitch with a result discovered in the years 1930 implies that there is no solution with the tenth problem of Hilbert. This result discovered by several logicians affirms that there recursively exist nonrecursive units énumérables. In this context, a unit S of integers “recursive” if there is an algorithm which, being given an integer N, yes returns an answer or not to the question N is called belongs to S? It follows that there are equations diophantiennes which can be solved by no algorithm.

The theorem of Youri Matiiassevitch was since employee to show the indecidability of many problems involved in the arithmetic one, in the same way, one can also derive the following stronger form from the first theorem of incomplétude of Gödel:

Is an unspecified axiomatization of arithmetic, one can build an equation diophantienne which does not have any solution, but such as this fact cannot be shown in axiomatization in question.

References

• Youri Matiiassevitch the tenth problem of Hilbert: Its indecidability , Masson, (1995), ISBN: 2225848351