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 an integer (n1,...nj) is in S if and only if there exist some integers x1,...,xk with f(n,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

Matiyasevich's theorem states that a set of integers is Diophantine if and only if it is recursively enumerable. The phrase recursively enumerable is not very suggestive. A set S of integers (or tuples of integers) is recursively enumerable precisely if one can write a computer program that, when given an integer (or tuple) n, eventually halts if n is a member of S, and runs forever otherwise.