Diophantine set
From Wikipedia, the free encyclopedia
In mathematics, a set S of j-tuples of integers is Diophantine precisely if there is some polynomial with integer coefficients f(n1, ..., nj, x1, ..., xk) such that a tuple (n1, ..., nj) of integers is in S if and only if there exist some integers x1, ..., xk with f(n1, ..., nj, x1, ..., xk) = 0. (Such a polynomial equation over the integers is also called a Diophantine equation.) In other words, a Diophantine set is a set of the form
where f is a polynomial function with integer coefficients.
Matiyasevich's theorem, published in 1970, states that a set of integers is Diophantine if and only if it is recursively enumerable. A set S is recursively enumerable precisely if there is an algorithm that, when given an integer, eventually halts if that input is a member of S and otherwise runs forever.
Matiyasevich's theorem effectively settled Hilbert's tenth problem.
[edit] References
- Hilbert's 10th Problem by Yuri Matiyasevich, MIT Press, 1993, ISBN 0-262-13295-8