Outstanding result. Hilbert's tenth problem solved!

14

Hilbert’s tenth problem solution!

This issue «Kvant» is already going to press when the mathematical world has become aware of all about the outstanding achievements of Soviet and, perhaps, world (!) mathematics: a recent graduate of Leningrad University, a twenty-year-old graduate student, Yuri Matiyasevich, proved the algorithmic undecidability of the signs of Hilbert’s tenth problem.

Yu. Matiyasevich, although young in age, is by no means a newbie in mathematics. While still at school, he became the winner of the International Mathematical Olympics, and then during his student years he obtained important and interesting results in mathematical logic. The very next year, 1968, he published three works in which, in essence, the “attack” of Hilbert’s 10th problem began. And here is the result, which literally tomorrow will be included in textbooks. By the way, in the collection “Hilbert’s Problems” published only last year by the Nuka publishing house, there is an article devoted to the 10th problem, which does not even mention that Hilbert’s tenth problem is algorithmically unsolvable.

It is curious that Yuri Matiyasevich specializes not in number theory, whose “department” would seem to include the problem of solvability of Diophantine equations, but in mathematical logic. He is a student of N. A. Shain and S. Yu. Maslov—a representative of the “Leningrad School” of mathematical logic and theory of algorithms, adhering to the so-called constructive direction in logic and mathematics, headed by Corresponding Member of the USSR Academy of Sciences A. A. Markov.

The “biography” of the problem is as follows.

In 1900, at the World Congress of Mathematicians in Paris, one of the world’s leading mathematicians, David Hilbert, identified twenty years of problems from various areas of mathematics, the solutions of which, in his opinion, would be of particular importance for the further development of this science *). Since then, these “Hilbert problems” have invariably attracted the attention of mathematicians around the world. Some of them have already been solved, while others stubbornly refuse to be solved.

Problem No. 10 is formulated as follows: “Let an equation with an arbitrary number be given

*) See D. Hilbert, “Mathematical problems”. Nuka, 1969.

unknowns and integer rational coefficients (i.e., an equation of the form $P(x_1, \dots, x_n) = 0$, where $P$ is a polynomial of arbitrary degree with integer coefficients in the unknowns $x_1, \dots, x_n$); it is required to indicate a way by which, using a finite number operation, one could find out whether an equation is solvable in integers or not (i.e., whether there is a set of integers $x_1^0, \dots, x_n^0$ such that $P(x_1^0, \dots, x_n^0) = 0$).”

Despite the simplicity and elementary formulation of the tenth problem, the sought-after “method” (or, as they say in modern mathematics, the algorithm could not be found, which, naturally, suggested that it simply did not exist. After a precisely mathematical definition became popular in the thirties of our degree, it became possible to talk about the search for such a negative solution to the 10th problem.

Congratulating Yu. Matiyasevich and his teacher on their outstanding contribution to science, the editors of «Kvant» will soon tell you in more detail about this outstanding result.