In mathematics, a setS 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.
To do this, suppose we set t = T + q in the above polynomial, where q is an arbitrary rational number.
As before, it would be simple to find a rational value of T that makes this expression a square, provided the leading and trailing coefficients are squares.
Notice that the trailing coefficient has the same form as the original polynomial in t, which we already know how to make into a square, by setting q = 3/2, which was our previous solution.
A set S of integers is recursively enumerable precisely if there is an algorithm that behaves as follows: When given as input an integer n, if n is a member of S, then the algorithm eventually halts; otherwise it runs forever.
In this context, a set S of integers is called "recursive" if there is an algorithm that, when given as input an integer n, returns as output a correct yes-or-no answer to the question of whether n is a member of S.
It follows that there are Diophantine equations which cannot be solved by any algorithm, unless one can construct a hypercomputer (Kieu, 2003); however, this is generally held physically implausible.
Feeds |
Contact