Hilbert's tenth problem
Is there an algorithm that takes any polynomial equation with integer coefficients, in any number of unknowns, and decides whether it has a solution in integers?
History and references
Solved in 1970 by Yuri Matiyasevich (completing work of Martin Davis, Hilary Putnam and Julia Robinson).
Hilbert asked for such a procedure in his 1900 list of problems, decades before there was a precise definition of an algorithm that would make a negative answer possible. Over about 21 years Martin Davis, Hilary Putnam and Julia Robinson reduced the problem to showing that a single set of exponential growth can be defined by a Diophantine equation. Yuri Matiyasevich supplied this final step in 1970. The resulting MRDP theorem says that every recursively enumerable set is Diophantine, so an algorithm for Diophantine equations would solve the halting problem, and no such algorithm exists. The analogous question for solutions in rational numbers is still open.
References
Solutions 0
Sign in or create an account to publish a solution