Matiyasevich’s Solution

What Yuri Matiyasevich did in 1970 in order to prove “Davis’s daring hypothesis”, namely, every r.e. set is Diophantine, was to use the Fibonacci numbers to construct a Diophantine equation which constituted a Diophantine definition of the set of pairs (u, v} for which v is the 2u-th Fibonacci number. His equation is obtained by summing the squares of the left sides of the following system of equations and setting the result equal to zero.

Julia Robinson’s early work had shown that JR implies that the exponential function is Diophantine. Thus, Matiyasevich’s proof of JR could be applied to the Davis- Putnam-Robinson theorem to conclude that every listable set, i.e., every r.e. set, is Diophantine. In particular there is a Diophantine definition of a listable set which is not computable. And so ends the story of Hilbert’s tenth problem.

Later, in 1976, Yuri presented a new proof [17] of the Davis-Putnam-Robinson theorem. And in 1984, Jones and Matiyasevich proved it once again using register machines [2]. Readers may also find interesting the brief expository article [18]. Finally, Matiyasevich has written a most complete and enjoyable book on Hilbert’s tenth problem and its history [19].

< Prev   CONTENTS   Source   Next >