Science Fair Project 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.
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details